fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4.  
  5. struct point
  6. {
  7.     ll x,y;
  8. };
  9.  
  10. point base;
  11.  
  12. int area( point p, point q, point r )
  13. {
  14.     ll x[]= {p.x, q.x, r.x};
  15.     ll y[]= {p.y, q.y, r.y};
  16.  
  17.     ll a= 0;
  18.     int j= 2;
  19.  
  20.     for(int i=0; i<3; i++)
  21.     {
  22.         a+=(x[j]+x[i])*(y[j]-y[i]);
  23.         j= i;
  24.     }
  25.  
  26.     if(a>0)
  27.         return 1;
  28.     if(a<0)
  29.         return 2;
  30.     return 0;
  31. }
  32.  
  33. bool cmp1( const point&a, const point&b  )
  34. {
  35.     if(a.y==b.y)
  36.         return a.x<b.x;
  37.     return a.y<b.y;
  38. }
  39.  
  40. bool cmp2( const point&a, const point&b )
  41. {
  42.     if( area( base, a, b )==2 )
  43.         return 1;
  44.     return 0;
  45. }
  46.  
  47.  
  48. void cHull( point points[], int n )
  49. {
  50.     vector<point> hull;
  51.     int l= 0;
  52.  
  53.     for(int i=1; i<n; i++)
  54.         if(points[i].y<points[l].y)
  55.             l= i;
  56.  
  57.     int p=l, q;
  58.  
  59.     do
  60.     {
  61.         vector <point> col;
  62.  
  63.         hull.push_back( points[p] );
  64.         q= (p+1)%n;
  65.  
  66.         for(int i=0; i<n; i++)
  67.         {
  68.             if(i==q or i==p)
  69.                 continue;
  70.             int pos= area( points[p], points[q], points[i] );
  71.             if( pos==2 )
  72.                 q= i;
  73.             else if(pos==0)
  74.             {
  75.                 ll dist1= (points[p].x-points[i].x)*(points[p].x-points[i].x)
  76.                           +(points[p].y-points[i].y)*(points[p].y-points[i].y);
  77.                 ll dist2= (points[p].x-points[q].x)*(points[p].x-points[q].x)
  78.                           +(points[p].y-points[q].y)*(points[p].y-points[q].y);
  79.  
  80.                 if(dist1>dist2)
  81.                 {
  82.                     col.push_back( points[q] );
  83.                     q= i;
  84.                 }
  85.                 else
  86.                     col.push_back(points[i]);
  87.             }
  88.         }
  89.  
  90.         p= q;
  91.  
  92.         for(int i=0;i<col.size();i++)
  93.             hull.push_back( col[i] );
  94.     }
  95.     while(points[p].x!=points[l].x or points[p].y!=points[l].y);
  96.  
  97.  
  98.  
  99.     sort( hull.begin(), hull.end(), cmp1 );
  100.     base= hull[0];
  101.     sort( hull.begin()+1, hull.end(), cmp2 );
  102.  
  103.     int sz= hull.size();
  104.  
  105.     int cnt= 0;
  106.     for(int i=0; i<sz; i++)
  107.     {
  108.         if(hull[i].x==base.x and hull[i].y==base.y)
  109.             continue;
  110.         cnt++;
  111.     }
  112.  
  113.     while(hull.size()<3)
  114.         hull.push_back(base);
  115.  
  116.  
  117.     cout<<max(cnt+2, 3)<<endl;
  118.     cout<<base.x<<" "<<base.y<<endl;
  119.  
  120.     int k=0;
  121.     sz= hull.size();
  122.  
  123.     for(int i=0; i<sz; i++)
  124.     {
  125.         //cout<<k<<endl;
  126.         if(hull[i].x==base.x and hull[i].y==base.y)
  127.         {
  128.             k++;
  129.             if(k<=2)
  130.                 continue;
  131.         }
  132.         cout<<hull[i].x<<" "<<hull[i].y<<endl;
  133.     }
  134.     cout<<base.x<<" "<<base.y<<endl;
  135. }
  136.  
  137. int main()
  138. {
  139.     int tc;
  140.     cin>>tc;
  141.     cout<<tc<<endl;
  142.     for(int t=1; t<=tc; t++)
  143.     {
  144.         int n;
  145.         cin>>n;
  146.         point points[n];
  147.  
  148.         for(int i=0; i<n; i++)
  149.         {
  150.             point p;
  151.             cin>>p.x>>p.y;
  152.             points[i]= p;
  153.         }
  154.  
  155.         int l;
  156.         if(t!=tc)
  157.             cin>>l;
  158.  
  159.         cHull(points, n);
  160.  
  161.         if(t!=tc)
  162.             cout<<l<<endl;
  163.     }
  164. }
  165.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
3
15
30 30
50 60
60 20
70 45
86 39
112 60
200 113
250 50
300 200
130 240
76 150
47 76
36 40
33 35
30 30
-1
12
50 60
60 20
70 45
100 70
125 90
200 113
250 140
180 170
105 140
79 140
60 85
50 60
-1
6
60 20
250 140
180 170
79 140
50 60
60 20
stdout
copy 
3
10
60 20
250 50
300 200
130 240
76 150
47 76
30 30
30 30
30 30
60 20
-1
10
60 20
250 140
125 90
100 70
180 170
79 140
50 60
50 60
50 60
60 20
-1
6
60 20
60 20
60 20
250 140
180 170
79 140
50 60
60 20
https://ideone.com/ykDzfM
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!