pku2007 Scrambled Polygon

http://poj.org/problem?id=2007
计算几何，凸包，逆时针排序
  1 #include <stdio.h>
  2 #include <vector>
  3 #include <queue>
  4 #include <algorithm>
  5 #include <math.h>
  6 
  7 using namespace std;
  8 
  9 const double eps = 1e-8;
 10 
 11 int cmp(double x)
 12 {
 13     if(fabs(x) < eps) return 0;
 14     if(x > 0) return 1;
 15     return -1;
 16 }
 17 
 18 
 19 struct point
 20 {
 21     double x, y;
 22     point() {}
 23     point(double a, double b): x(a), y(b) {}
 24     friend point operator - (const point &a, const point &b)
 25     {
 26         return point(a.x-b.x, a.y-b.y);
 27     }
 28     friend bool operator == (const point &a, const point &b)
 29     {
 30         return cmp(a.x-b.x) ==0 && cmp(a.y-b.y) ==0;
 31     }
 32 };
 33 
 34 double det(const point &a, const point &b)
 35 {
 36     return a.x*b.y - a.y*b.x;
 37 }
 38 
 39 struct polygon_convex
 40 {
 41     vector<point> P;
 42     polygon_convex(int Size=0)   
 43     {
 44         P.resize(Size);
 45     }
 46 }polygon1;
 47 
 48 bool comp_less(const point &a, const point &b)
 49 {
 50     return cmp(a.x-b.x)<0 || cmp(a.x-b.x)==0 && cmp(a.y-b.y)<0;
 51 }
 52 
 53 polygon_convex convex_hull(vector<point> a)
 54 {
 55     polygon_convex res(2*a.size()+5);
 56     sort(a.begin(), a.end(), comp_less);
 57     a.erase(unique(a.begin(), a.end()), a.end());
 58     int m=0;
 59     for(int i=0; i<a.size(); ++i)
 60     {
 61         while(m>1 && cmp(det(res.P[m-1]-res.P[m-2], a[i]-res.P[m-2])) <= 0) --m;
 62         res.P[m++] = a[i];
 63     }
 64     int k = m;
 65     for(int i=int(a.size())-2; i>=0; --i)
 66     {
 67         while(m>k && cmp(det(res.P[m-1]-res.P[m-2], a[i]-res.P[m-2])) <= 0) --m;
 68         res.P[m++] = a[i];
 69     }
 70     res.P.resize(m);
 71     if(a.size()>1) res.P.resize(m-1);
 72     return res;
 73 }
 74 
 75 vector<point> v1, r1;
 76 
 77 int main()
 78 {
 79     double x, y;
 80     int i, flag;
 81     while(~scanf("%lf%lf", &x, &y))
 82     {
 83         point p(x, y);
 84         v1.push_back(p);
 85     }
 86     polygon1 = convex_hull(v1);
 87     r1 = polygon1.P;
 88     flag = 0;
 89     for(i=0; i<r1.size(); i++)
 90     {
 91         if(r1[i].x == 0.0 && r1[i].y == 0.0)
 92         {
 93             flag = 1;
 94         }
 95         if(flag)
 96         {
 97             printf("(%.0lf,%.0lf)\n", r1[i].x, r1[i].y);
 98         }
 99     }
100     for(i=0; i<r1.size(); i++)
101     {
102         if(r1[i].x == 0.0 && r1[i].y == 0.0)
103         {
104             break;
105         }
106         printf("(%.0f,%.0f)\n", r1[i].x, r1[i].y);
107     }
108     return 0;
109 }