Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Aleksandar 'Al3kSaNdaR' Ivanovic
- mit-indiv09-dots
- */
- #include <cstdio>
- #include <algorithm>
- #include <math.h>
- using namespace std;
- const int MAX_N = 100000;
- const double EPS = 1e-8;
- const double PI = 3.141592653589;
- typedef struct Point
- {
- double X;
- double Y;
- double Angle;
- Point ( ) { };
- Point ( double _X, double _Y, double _Angle )
- {
- X = _X;
- Y = _Y;
- Angle = _Angle;
- }
- inline friend bool operator < ( const Point & First, const Point & Second )
- {
- if ( First.Angle > Second.Angle ) return 1;
- else return -1;
- }
- };
- int N;
- Point Points[MAX_N];
- double Abs ( double Number )
- {
- if ( Number >= 0 ) return Number;
- else return -1 * Number;
- }
- bool Left ( int idx, int idy, int idz )
- {
- double Det = ( Points[idy].X - Points[idx].X ) * ( Points[idz].Y - Points[idx].Y ) - ( Points[idy].Y - Points[idx].Y ) * ( Points[idy].X - Points[idx].X );
- if ( Det < - EPS ) return 1;
- if ( Det > EPS ) return -1;
- return 0;
- }
- int main ( void )
- {
- scanf ( "%d", &N );
- for ( int i = 0; i < N; i++ )
- {
- double X, Y;
- scanf ( "%lf %lf", &X, &Y );
- Points[i] = Point ( X, Y, 0 );
- }
- int idx = 0;
- for ( int i = 1; i < N; i++ ) if ( ( Points[idx].Y > Points[i].Y ) || ( ( Abs ( Points[idx].Y - Points[i].Y ) <= EPS ) && ( Points[idx].X < Points[i].X ) ) ) idx = i;
- Point tPoint = Points[idx];
- Points[idx] = Points[0];
- Points[0] = tPoint;
- for ( int i = 1; i < N; i++ )
- {
- Points[i].X -= Points[0].X;
- Points[i].Y -= Points[0].Y;
- Points[i].Angle = atan2 ( Points[i].Y , Points[i].X );
- if ( Points[i].Angle < 0 ) Points[i].Angle += 2 * PI;
- }
- Points[0].X = 0;
- Points[0].Y = 0;
- sort ( Points, Points + N );
- Hull[0] = 0;
- Hull[1] = 1;
- idx = 1;
- for ( int i = 2; i < N; i++ )
- {
- while ( ( idx >= 1 ) && ( Left ( Hull[idx - 1], Hull[k], i ) == 1 ) ) idx--;
- idx++;
- Hull[idx] = i;
- }
- while ( ( idx >= 1 ) && ( Left ( Hull[idx - 1], Hull[k], i ) == 1 ) ) idx--;
- idx++;
- for ( int i = 0; i < N; i++ )
- {
- Points[i].X += tPoint.X;
- Points[i].Y += tPoint.Y;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement