Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <algorithm>
- #include <vector>
- using namespace std;
- typedef pair<int,int> par;
- #define x first
- #define y second
- int ccw( par A, par B, par C ) {
- B.x -= A.x; B.y -= A.y;
- C.x -= A.x; C.y -= A.y;
- return B.x*C.y - B.y*C.x;
- }
- int main( void ) {
- int n; scanf( "%d", &n );
- vector<par> V;
- for( int i = 0; i < n; ++i ) {
- par p; scanf( "%d %d", &p.x, &p.y );
- V.push_back( p );
- }
- int ans = 0;
- for( ; V.size() >= 3; ++ans ) {
- sort( V.begin(), V.end() );
- vector<par> A = V;
- for( int i = V.size()-2; i >= 0; --i )
- A.push_back( V[i] );
- vector<par> H;
- for( int i = 0; i < A.size(); ++i ) {
- while( H.size() >= 2 && ccw( H[H.size()-2], H[H.size()-1], A[i] ) < 0 ) H.pop_back();
- H.push_back( A[i] );
- }
- H.pop_back();
- A.clear();
- sort( H.begin(), H.end() );
- for( int i = 0, j = 0; i < V.size(); ++i ) {
- for( ; j < H.size() && H[j] < V[i]; ++j );
- if( j == H.size() || H[j] != V[i] ) A.push_back( V[i] );
- }
- V = A;
- }
- printf( "%d\n", ans );
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement