hihoCoder 1508-剑刃风暴

---

简化题意：给定平面上n个点，和一个半径为r的圆，这个圆可以任意放置，问最多能覆盖多少个点。 这题类似poj1981（单位圆），我是参考这个题解来做的。 暴力方法。最优的圆肯定是能覆盖最多的点，且有些点落在圆周上，导致这个圆只要稍微往旁边移一下，覆盖的点就会减少。所以枚举任意两个点，假设这两个点正好落在最优圆的圆周上，则由此可以确定一个圆心，然后统计所有落在这个圆内的点的个数，并更新最大值。时间复杂度是$$O(n^3)$$。 有一点需要注意的是两个圆周上的点，如果它们的距离不是刚好等于直径，则能确定两个圆心，但只需算一个就好了。比如有三个点A,B,C确定的最优圆是下图中的实线，如果我们在由两点确定圆心的过程中，始终统一确定“下边”的圆，则虽然A,B确定的圆是虚线的（虽然A,B确定的圆还可以是实线，但根据我们的规定，统一取“下边”的圆），不是最优。但当遍历到A,C点对时，根据规则，这两个点确定的圆是实线的，也就是说，只要根据统一的规则确定圆心，肯定能找到那个最优圆的。 已知两点求圆心的方法请看这篇博客中的GetCenter函数，下图作了一些辅助线帮助理解。关于atan和atan2的区别，请看这篇博客。 暴力方法在hiho上TLE，需要寻求更高效的算法。 假设以两个点i,j为圆心画半径为R的圆，如果两个圆相交，则在相交的弧上任意一点画圆，都能覆盖原来的i,j两点。基于这个思想，假设现在固定点i为圆心，R为半径画圆，求出所有以其他点为圆心画的圆和圆i相交的弧，则在相交重叠次数最多的那段弧上的点为圆心画的圆肯定能覆盖最多的点，覆盖的点数就是这段弧被重叠的次数。每个点i都能求出这样一个最大值，则所有点的这个最大值的最大值就是全局能覆盖的最多点。 怎样表示两个圆相交的那段弧呢，使用极坐标，因为弧是由两条半径张成的，所以可以表示成两条半径的极坐标夹角，并且标明夹角的开始（is=1）和结束（is=-1）。求重叠次数最多的弧的方法是，把所有重叠弧的起止半径的极坐标夹角排个序，然后遍历一下，当夹角开始（is=1）次数最多且结束（is=-1）次数最少时，说明重叠次数最多，所以就是is的累加和的最大值。 完整代码借鉴这篇博客，注意原代码是针对R=1的情况，如果是任意的R，则计算角差那里还需除以半径R。完整代码如下： [cpp] #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <iostream> using namespace std; const int MAX_N = 2005; const double PI = acos(-1.0); //const double R = 1.0;//定义覆盖圆半径为R int T, n, total, R; struct Point { double x, y; }point[MAX_N]; struct Angle { double data; int is; bool operator < (const Angle& rhs) const { return data<rhs.data; } }angle[MAX_N * 2]; inline double Dis(Point a, Point b)//计算线段ab的长度 { return sqrt((a.x – b.x)*(a.x – b.x) + (a.y – b.y)*(a.y – b.y)); } inline double God(Point a, Point b)//计算向量ab的极角 { double res = atan(fabs((b.y – a.y) / (b.x – a.x))); if (b.y<a.y) { if (b.x<a.x) res += PI; else res = 2 * PI – res; } else { if (b.x<a.x) res = PI – res; } return res; } void solve() { int res = 1; for (int i = 0; i<n; i++) { total = 0; for (int j = 0; j<n; j++) { if (i == j) continue; double dist = Dis(point[i], point[j]); if (dist>2.0 * R) continue; double base = God(point[i], point[j]); double extra = acos((dist / 2.0) / R); //计算差角 angle[total].data = base – extra; // in angle[total++].is = 1; angle[total].data = base + extra; // out angle[total++].is = -1; } if (total <= res) continue; sort(angle, angle + total); int tmp = 1; for (int j = 0; j<total; j++) { tmp += angle[j].is; res = max(res, tmp); } } printf("%d\n", res); } int main() { //freopen("input.txt", "r", stdin); scanf("%d %d", &n, &R); for (int i = 0; i<n; i++) { scanf("%lf %lf", &point[i].x, &point[i].y); } solve(); return 0; } [/cpp] 本代码提交AC，用时1345MS。 平时几乎没做过计算几何的题目，发现好难呀。 ]]>