多边形
Time Limit: 1000 MS Memory Limit: 65536 K
Total Submit: 113(42 users) Total Accepted: 51(38 users) Rating:
Special Judge: No
Description
一个封闭的多边形定义是被有限个线段包围。线段的相交点称作多边形的顶点，当你从多边形的一个顶点沿着线段行走时，最终你会回
到出发点。
凸多边形（convex）想必大家已经很熟悉了，下图给出了凸多边形和非凸多边形实例。
这里讨论的是在平面坐标的封闭凸多边形，多变形的顶点一个顶点在原点（x=0,y=0）.图2显示的那样。这样的图形有两种性质。
第一种性质是多边形的顶点会在平面上少于等于三个象限，就如图二那样，第二向县里面没有多边形的点（x<0,y>0）。
为了解释第二种性质，假设你沿着多边形旅行，从原点（0,0）出发遍历每个顶点一次，当你遍历到除原点（0,0）时候，从这一点画一条和原点（0,0）的斜线。计算这种斜率。当计算完所有的斜率时候，这些斜率组成升序或降序顺序。
如图三所示。
Input
输入包含多组测试数据。
第一行输入一个整数n(50>n>0),其中n表示多边形顶点的个数,当n为0时表示结束。紧跟n行输入在平面中多边形的顶点整数x,y(-999<x,y<999)，其中第一行是原点（0,0），其他的多边形顶点可能不是顺序给出。没有顶点在x,y坐标轴上，没有三个顶点共线。
Output
输出多边形的顶点，每个顶点一行，原点（0,0）首先输出。其他顶点的输出构成沿多边形（逆时针方向）构成一条旅游路线。输出格式为（x,y）如实例
Sample Input
10
0 0
70 -50
60 30
-30 -50
80 20
50 -60
90 -20
-30 -40
-10 -60
90 10
0
Sample Output
(0,0)
(-30,-40)
(-30,-50)
(-10,-60)
(50,-60)
(70,-50)
(90,-20)
(90,10)
(80,20)
(60,30)
Author
鲁学涛
计算几何，极角排序。
极角排序的基础练习题，我用atan2做的，据说这可能会伤精度，so可以采用象限极角排序，不失精度。有兴趣的同学可以查查。
手工排序代码：
1 #include2 #include 3 typedef struct { 4 double x,y; 5 }Point; 6 int main() 7 { 8 int n; 9 while(scanf("%d",&n)!=EOF){10 if(n==0) break;11 Point p[51];12 int i,j,num[51];13 for(i=1;i<=n;i++){ //输入点集14 scanf("%lf%lf",&p[i].x,&p[i].y);15 num[i] = i; //排序的时候记录顺序16 }17 double a[51];18 a[1] = 0;19 for(i=2;i<=n;i++)20 a[i] = atan2(p[i].y,p[i].x); //利用math库中的atan2(y,x)函数，求坐标(x,y)与x正半轴逆时针方向的夹角。21 for(i=2;i<=n-2;i++) //注意从2开始排序22 for(j=2;j<=n-i+1;j++)23 if(a[j]>a[j+1]){24 double t;25 t = a[j];a[j] = a[j+1];a[j+1] = t;26 int tt;27 tt=num[j];num[j]=num[j+1];num[j+1]=tt;28 }29 for(i=1;i<=n;i++) //输出30 printf("(%d,%d)\n",(int)p[num[i]].x,(int)p[num[i]].y);31 }32 return 0;33 }
利用sort函数排序代码：
1 #include2 #include 3 #include 4 using namespace std; 5 typedef struct { 6 double x,y; 7 }Point; 8 bool cmp(Point a,Point b) //利用atan2的比较函数 9 {10 double d1 = atan2(a.y,a.x);11 double d2 = atan2(b.y,b.x);12 return d1 < d2;13 }14 int main()15 {16 int n;17 while(scanf("%d",&n)!=EOF){18 if(n==0) break;19 Point p[51];20 int i;21 for(i=1;i<=n;i++){ //输入点集22 scanf("%lf%lf",&p[i].x,&p[i].y);23 }24 sort(p+2,p+n+1,cmp); //排序25 for(i=1;i<=n;i++) //输出26 printf("(%d,%d)\n",(int)p[i].x,(int)p[i].y);27 }28 return 0;29 }
Freecode :