input 2 8 8 3 7 3 5 6 2 7 2 5 6 6 3 2 5 5 4 2 4 5 5 2 3 1 4 output Case #1: 13.50000000 Case #2: 16.00000000
解题思路 这道题的样例暗示应该以Bob为顶点去求解。但是实际上，第一个样例的答案是错误的： （来源：知乎用户cometeme的回答https://www.zhihu.com/question/426081900）虽然这道题假了，但是还是试着以Bob为顶点过下这道题吧。 以Bob为顶点，和其他n个点做射线，此时相当于坐标系转变为Bob是原点。根据射线的极角和三角函数计算从x轴正半轴转到该射线的位置在四条边框上所截取的长度，分8中情况讨论。对这些长度排序，即相当于对极角排序。枚举两条相邻的射线a，b(包括尾、首射线)，可以保证a->b之间是空白的（没有其他点），注意这里一定要保证是a到b的顺序，是有向的。a和b截取的长度做差即可求得结果，对于首尾射线特殊考虑下即可。（wjx的思路） 还有一种思路和上面类似，对所有射线极角排序（因为可能出现相同极角的射线，根据后面的算法，必须去重），对四条边框依次标号。根据三角形相似求出相邻两条射线和边框的交点依次是A,B，考虑A，B在分别在哪条边框上，分16种情况，计算从A->B在边框上的有向距离。注意，一定是A->B，在同一条边框上时不是直接求|AB|。（syh的思路） 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn) 我原本的思路是判断两个交点A、B的位置，分三种情况：同一条边框，相邻边框、平行边框。但是这么分情况的话在算A->B的有向距离时很可能出错，wa了很多次，wjx和syh的思路又清晰又100%正确，遂放弃我的思路(꒦_꒦) 。
ac代码 wjx的代码上小改了一下，懒得重新写了。 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5+10; const double eps = 1e-8; const double pi = acos(-1.0); int n; double w, h, bx, by; double cx, cy, dx, dy; // (cx,cy)矩形左下角，(dx,dy)矩形右上角 double a[maxn]; // 极角度数 int dcmp(double x)//精度三态函数(>0,<0,=0) { if (fabs(x) < eps) return 0; //等于 else return x < 0 ? -1 : 1;//小于，大于 } double get_angle(double x, double y) // 计算点(x,y)对应极角 { double ang = atan2(y, x); if(dcmp(ang)<0) ang = 2*pi+ang; return ang; } double get_length(double a) // 计算极角a对应的所截取长度（从点(dx,0)开始） { double res = 0; if(a <= get_angle(dx, dy)) // 右边上段 return res + dx * tan(a); else res += dy; if(a <= pi / 2) // 上边右段 return res + dx - dy * tan(pi / 2 - a); else res += dx; if(a <= get_angle(cx, dy)) // 上边左段 return res + dy * tan(a - pi / 2); else res += (-cx); if(a <= pi) // 左边上段 return res + dy - (-cx) * tan(pi - a); else res += dy; if(a <= get_angle(cx, cy)) // 左边下段 return res + (-cx) * tan(a - pi); else res += (-cy); if(a <= pi * 3 / 2) // 下边左段 return res + (-cx) - (-cy) * tan(pi * 3 / 2 - a); else res += (-cx); if(a <= get_angle(dx, cy)) // 下边右段 return res + (-cy) * tan(a - pi * 3 / 2); else res += dx; return res + (-cy) - dx * tan(pi * 2 - a); // 右边下段 } int main() { //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin); int T, kase = 0; scanf("%d", &T); while(T--) { scanf("%lf%lf", &w, &h); scanf("%lf%lf", &bx, &by); scanf("%d", &n); cx = 0 - bx; cy = 0 - by; dx = w - bx; dy = h - by; for(int i = 1; i <= n; i++) { double x, y; scanf("%lf%lf", &x, &y); a[i] = get_length(get_angle(x - bx, y - by)); } sort(a + 1, a + n + 1); double ans = 0; for(int i = 1; i < n; i++) ans = max(ans, a[i+1] - a[i]); ans = max(ans, 2 * (w + h) - (a[n] - a[1])); printf("Case #%d: %.8f\n", ++kase, ans); } return 0; } /* 6 8 8 3 7 3 5 6 2 7 2 5 6 6 3 2 5 5 4 2 4 5 5 2 3 1 4 4 4 2 2 2 1 1 3 3 4 4 2 2 1 1 1 5 5 3 3 2 1 1 2 2 4 3 1 1 2 1 2 2 2 4 3 1 1 2 1 2 2 2 */