Advertisement
promitheus_sal

Untitled

Oct 18th, 2023
567
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.30 KB | Source Code | 0 0
  1. typedef struct point {
  2.     int x,y;
  3.     point(int a, int b): x{a},y{b} {}
  4. } point;
  5.  
  6. int ccw(const point& a, const point& b, const point& c) {
  7.     return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
  8. }
  9.  
  10. double dist(const point& a, const point& b) {
  11.     int dx = a.x-b.x;
  12.     int dy = a.y-b.y;
  13.     return sqrt(dy*dy+dx*dx);
  14. }
  15.  
  16. int N;
  17. int main() {
  18.     scanf("%d",&N);
  19.     vector<point> A;
  20.     vector<point> B;
  21.     for(int i=0;i<N;i++) {
  22.         int a,b;
  23.         scanf("%d%d",&a,&b);
  24.         A.push_back(point(a,b));
  25.     }
  26.     sort(A.begin(),A.end(),(const point&a,const point& b) {
  27.         return a.y!=b.y?a.y<b.y:a.x<b.x;
  28.     });
  29.     point sa = A[0];
  30.  
  31.     sort(A.begin()+1,A.end(),(const point&a , const point&b) {
  32.         ccw(sa,a,b)<0;
  33.     });
  34.    
  35.     vector<point> gs;
  36.     gs.push_back(A[0]);
  37.     gs.push_back(A[1]);
  38.     for(int i=2;i<N;i++) {
  39.         gs.push_back(A[i]);
  40.         while(true) {
  41.             int n = gs.size();
  42.             if(ccw(gs[n-2],gs[n-1],gs[n-3])>0) {
  43.                 gs[n-2]=gs[n-1];
  44.                 gs.pop_back();
  45.             }
  46.             else break;
  47.         }
  48.     }
  49.  
  50.     point old=gs[N-1];
  51.     double len = 0.0;
  52.     for(int i=0;i<N;i++) {
  53.         len+=dist(old,gs[i]);
  54.     }
  55.     long long int a = round(len);
  56.     printf("%lld\n",a);
  57.     return 0;
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement