POJ 2007 Scrambled Polygon

题目链接: http://poj.org/problem?id=2007

-----------------------------------------------------------------------------------------------

这题并没有卡精度也不需要多少讨论然而$WA$了很多发

刚看这题的时候感觉貌似就是一个极角排序然后就$WA$了 (其实以前也没写过极角排序)

然后随手找到一个反例加了些讨论继续$WA$

最后发现其实完全不是什么讨论是否充分的问题

因为$0$向量的方向是任意的而不是$0$

所以我们要以凸多边形内部(含边界但不含端点)的某点为原点进行极角排序

然后就不需要什么讨论了

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <algorithm>
 5 using namespace std;
 6 const double pi = acos(-1);
 7 struct point
 8 {
 9     int x, y;
10     double rad;
11 }a[60];
12 int n = 1;
13 double xx, yy;
14 bool cmp(const point &aa,const point &bb)
15 {
16     return aa.rad < bb.rad;
17 }
18 int main()
19 {
20     scanf("%d%d", &a[0].x, &a[0].y);
21     while(scanf("%d%d", &a[n].x, &a[n].y) != EOF)
22         ++n;
23     --n;
24     xx = (a[0].x + a[1].x) * 0.5;
25     yy = (a[0].y + a[1].y) * 0.5;
26     for(int i = 0; i <= n; ++i)
27         a[i].rad = atan2(a[i].y - yy, a[i].x - xx);
28     sort(a, a + 1 + n, cmp);
29     int flag = 0;
30     while(a[flag].x != 0 || a[flag].y != 0)
31         ++flag;
32     for(int i = flag; i <= n; ++i)
33         printf("(%d,%d)
", a[i].x, a[i].y);
34     for(int i = 0; i < flag; ++i)
35         printf("(%d,%d)
", a[i].x, a[i].y);
36     return 0;
37 }