简单几何(极角排序) POJ 2007 Scrambled Polygon-白红宇

简单几何(极角排序) POJ 2007 Scrambled Polygon

阅读量：7105 次

发布时间：2019-06-28

本文共 1771 字，大约阅读时间需要 5 分钟。

题意：裸的对原点的极角排序，凸包貌似不行。

/************************************************* Author        :Running_Time* Created Time  :2015/11/3 星期二 14:46:47* File Name     :POJ_2007.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e5 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;const double EPS = 1e-10;const double PI = acos (-1.0);int dcmp(double x) { if (fabs (x) < EPS) return 0; else return x < 0 ? -1 : 1;}struct Point { double x, y; Point () {} Point (double x, double y) : x (x), y (y) {} Point operator - (const Point &r) const { //向量减法 return Point (x - r.x, y - r.y); } bool operator == (const Point &r) const { //判断同一个点 return dcmp (x - r.x) == 0 && dcmp (y - r.y) == 0; } bool operator < (const Point &r) const { return x < r.x || (dcmp (x - r.x) == 0 && y < r.y); }};typedef Point Vector;Point read_point(void) { double x, y; scanf ("%lf%lf", &x, &y); return Point (x, y);}double polar_angle(Vector A) { return atan2 (A.y, A.x);}double dot(Vector A, Vector B) { return A.x * B.x + A.y * B.y;}double cross(Vector A, Vector B) { return A.x * B.y - A.y * B.x;}bool cmp(Point a, Point b) { return cross (a - Point (0, 0), b - Point (0, 0)) > 0;}int main(void) { vector
                      
                        ps; double x, y; while (scanf ("%lf%lf", &x, &y) == 2) { ps.push_back (Point (x, y)); } sort (ps.begin ()+1, ps.end (), cmp); for (int i=0; i