Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <cmath>
- #include <cstdio>
- using namespace std;
- #define pii pair<int,int>
- #define mp make_pair
- #define fi first
- #define se second
- pii a[1000];
- pii m;
- double dist(pii a, pii b)
- {
- return sqrt((a.fi-b.fi)*(a.fi-b.fi) + (a.se-b.se)*(a.se-b.se));
- }
- bool sr(pii m, pii a, pii b)
- {
- int t = (m.fi-a.fi)*(m.se+a.se)+(a.fi-b.fi)*(a.se+b.se)+(b.fi-m.fi)*(b.se+m.se);
- if (t != 0)
- {
- return t > 0;
- }
- else
- {
- return dist(m,a) > dist(m,b);
- }
- }
- bool srr(pii a, pii b)
- {
- return sr(m,a,b);
- }
- int main()
- {
- int n,x,y;
- scanf("%d",&n);
- for (int i = 0; i < n; i++)
- {
- scanf("%d%d",&x,&y);
- a[i] = mp(x,y);
- }
- m = a[0];
- for (int i = 0; i < n; i++)
- {
- if (m.fi > a[i].fi)
- {
- m = a[i];
- }
- else if (m.fi == a[i].fi && m.se > a[i].se)
- {
- m = a[i];
- }
- }
- sort(a,a+n,srr);
- vector<pii> v;
- for (int i = 0; i < n; i++)
- {
- if (v.size() < 2)
- {
- v.push_back(a[i]);
- }
- else
- {
- if (!sr(v[v.size()-2],v[v.size()-1],a[i]))
- {
- v.pop_back();
- i--;
- }
- else
- {
- v.push_back(a[i]);
- }
- }
- }
- double res = 0;
- for (int i = 0; i < v.size()-1; i++) res += dist(v[i],v[i+1]);
- res += dist(v[0],v[v.size()-1]);
- cout.precision(20);
- cout << res;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement