Advertisement
Guest User

Untitled

a guest
Jun 25th, 2017
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. typedef pair<int,int> par;
  8. #define x first
  9. #define y second
  10.  
  11. int ccw( par A, par B, par C ) {
  12.   B.x -= A.x; B.y -= A.y;
  13.   C.x -= A.x; C.y -= A.y;
  14.   return B.x*C.y - B.y*C.x;
  15. }
  16.  
  17. int main( void ) {
  18.   int n; scanf( "%d", &n );
  19.   vector<par> V;
  20.   for( int i = 0; i < n; ++i ) {
  21.     par p; scanf( "%d %d", &p.x, &p.y );
  22.     V.push_back( p );
  23.   }
  24.  
  25.   int ans = 0;
  26.   for( ; V.size() >= 3; ++ans ) {
  27.     sort( V.begin(), V.end() );
  28.     vector<par> A = V;
  29.     for( int i = V.size()-2; i >= 0; --i )
  30.       A.push_back( V[i] );
  31.  
  32.     vector<par> H;
  33.     for( int i = 0; i < A.size(); ++i ) {
  34.       while( H.size() >= 2 && ccw( H[H.size()-2], H[H.size()-1], A[i] ) < 0 ) H.pop_back();
  35.       H.push_back( A[i] );
  36.     }
  37.     H.pop_back();
  38.  
  39.     A.clear();
  40.     sort( H.begin(), H.end() );
  41.     for( int i = 0, j = 0; i < V.size(); ++i ) {
  42.       for( ; j < H.size() && H[j] < V[i]; ++j );
  43.       if( j == H.size() || H[j] != V[i] ) A.push_back( V[i] );
  44.     }
  45.     V = A;
  46.   }
  47.   printf( "%d\n", ans );
  48.  
  49.   return 0;
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement