首页 > 代码库 > 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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。