Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- typedef struct point {
- int x,y;
- point(int a, int b): x{a},y{b} {}
- } point;
- int ccw(const point& a, const point& b, const point& c) {
- return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
- }
- double dist(const point& a, const point& b) {
- int dx = a.x-b.x;
- int dy = a.y-b.y;
- return sqrt(dy*dy+dx*dx);
- }
- int N;
- int main() {
- scanf("%d",&N);
- vector<point> A;
- vector<point> B;
- for(int i=0;i<N;i++) {
- int a,b;
- scanf("%d%d",&a,&b);
- A.push_back(point(a,b));
- }
- sort(A.begin(),A.end(),(const point&a,const point& b) {
- return a.y!=b.y?a.y<b.y:a.x<b.x;
- });
- point sa = A[0];
- sort(A.begin()+1,A.end(),(const point&a , const point&b) {
- ccw(sa,a,b)<0;
- });
- vector<point> gs;
- gs.push_back(A[0]);
- gs.push_back(A[1]);
- for(int i=2;i<N;i++) {
- gs.push_back(A[i]);
- while(true) {
- int n = gs.size();
- if(ccw(gs[n-2],gs[n-1],gs[n-3])>0) {
- gs[n-2]=gs[n-1];
- gs.pop_back();
- }
- else break;
- }
- }
- point old=gs[N-1];
- double len = 0.0;
- for(int i=0;i<N;i++) {
- len+=dist(old,gs[i]);
- }
- long long int a = round(len);
- printf("%lld\n",a);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement