首页 > 代码库 > poj 2007 Scrambled Polygon 极角排序

poj 2007 Scrambled Polygon 极角排序

 1 /**
 2 极角排序输出,,,
 3 主要atan2(y,x) 容易失精度,,用
 4 bool cmp(point a,point b){
 5     if(cross(a-tmp,b-tmp)>0)
 6         return 1;
 7     if(cross(a-tmp,b-tmp)==0)
 8         return length(a-tmp)<length(b-tmp);
 9     return 0;
10 }
11 **/
12 #include <iostream>
13 #include <algorithm>
14 #include <cmath>
15 using namespace std;
16 
17 struct point {
18     double x,y;
19     point (double x=0,double y=0):x(x),y(y){}
20 };
21 point p[100];
22 point tmp;
23 typedef point Vector;
24 Vector operator - (point a,point b){
25     return Vector (a.x-b.x,a.y-b.y);
26 }
27 double angle(Vector v){
28     return atan2(v.y,v.x);
29 }
30 double length(Vector v){
31     return sqrt(v.x*v.x+v.y*v.y);
32 }
33 
34 double cross(Vector a,Vector b){
35     return a.x*b.y-a.y*b.x;
36 }
37 bool cmp(point a,point b){
38     if(cross(a-tmp,b-tmp)>0)
39         return 1;
40     if(cross(a-tmp,b-tmp)==0)
41         return length(a-tmp)<length(b-tmp);
42     return 0;
43 }
44 
45 int main()
46 {
47     int cnt =0;
48     double x1,y1;
49     cin>>tmp.x>>tmp.y;
50     while(cin>>x1>>y1){
51         p[cnt].x = x1;
52         p[cnt].y = y1;
53         cnt++;
54     }
55     sort(p,p+cnt,cmp);
56     cout<<"("<<tmp.x<<","<<tmp.y<<")"<<endl;
57     for(int i=0;i<cnt;i++)
58         cout<<"("<<p[i].x<<","<<p[i].y<<")"<<endl;
59     return 0;
60 }