Advertisement
Guest User

Untitled

a guest
May 28th, 2017
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.34 KB | None | 0 0
  1. /*
  2.     Aleksandar 'Al3kSaNdaR' Ivanovic
  3.  
  4.     mit-indiv09-dots
  5. */
  6. #include <cstdio>
  7. #include <algorithm>
  8. #include <math.h>
  9.  
  10. using namespace std;
  11.  
  12. const int MAX_N = 100000;
  13.  
  14. const double EPS = 1e-8;
  15. const double PI = 3.141592653589;
  16.  
  17. typedef struct Point
  18. {
  19.     double X;
  20.     double Y;
  21.     double Angle;
  22.  
  23.     Point ( ) { };
  24.  
  25.     Point ( double _X, double _Y, double _Angle )
  26.     {
  27.         X = _X;
  28.  
  29.         Y = _Y;
  30.  
  31.         Angle = _Angle;
  32.     }
  33.  
  34.     inline friend bool operator < ( const Point & First, const Point & Second )
  35.     {
  36.         if ( First.Angle > Second.Angle ) return 1;
  37.         else return -1;
  38.     }
  39. };
  40.  
  41. int N;
  42.  
  43. Point Points[MAX_N];
  44.  
  45. double Abs ( double Number )
  46. {
  47.     if ( Number >= 0 ) return Number;
  48.     else return -1 * Number;
  49. }
  50.  
  51. bool Left ( int idx, int idy, int idz )
  52. {
  53.     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 );
  54.  
  55.     if ( Det < - EPS ) return 1;
  56.  
  57.     if ( Det > EPS ) return -1;
  58.  
  59.     return 0;
  60. }
  61.  
  62. int main ( void )
  63. {
  64.     scanf ( "%d", &N );
  65.  
  66.     for ( int i = 0; i < N; i++ )
  67.     {
  68.         double X, Y;
  69.  
  70.         scanf ( "%lf %lf", &X, &Y );
  71.  
  72.         Points[i] = Point ( X, Y, 0 );
  73.     }
  74.  
  75.     int idx = 0;
  76.  
  77.     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;
  78.  
  79.     Point tPoint = Points[idx];
  80.  
  81.     Points[idx] = Points[0];
  82.  
  83.     Points[0] = tPoint;
  84.  
  85.     for ( int i = 1; i < N; i++ )
  86.     {
  87.         Points[i].X -= Points[0].X;
  88.  
  89.         Points[i].Y -= Points[0].Y;
  90.  
  91.         Points[i].Angle = atan2 ( Points[i].Y , Points[i].X );
  92.  
  93.         if ( Points[i].Angle < 0 ) Points[i].Angle += 2 * PI;
  94.     }
  95.  
  96.     Points[0].X = 0;
  97.  
  98.     Points[0].Y = 0;
  99.  
  100.     sort ( Points, Points + N );
  101.  
  102.     Hull[0] = 0;
  103.  
  104.     Hull[1] = 1;
  105.  
  106.     idx = 1;
  107.  
  108.     for ( int i = 2; i < N; i++ )
  109.     {
  110.         while ( ( idx >= 1 ) && ( Left ( Hull[idx - 1], Hull[k], i ) == 1 ) ) idx--;
  111.  
  112.         idx++;
  113.  
  114.         Hull[idx] = i;
  115.     }
  116.  
  117.     while ( ( idx >= 1 ) && ( Left ( Hull[idx - 1], Hull[k], i ) == 1 ) ) idx--;
  118.  
  119.     idx++;
  120.  
  121.     for ( int i = 0; i < N; i++ )
  122.     {
  123.         Points[i].X += tPoint.X;
  124.  
  125.         Points[i].Y += tPoint.Y;
  126.     }
  127.  
  128.     return 0;
  129. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement