HDU1883 Phone Cell

如上图，设A、B为点集中的两个点，分别以A、B为圆心作单位圆，则相交范围内的任意位置作新的单位圆，都可以同时包含A与B，如圆C，如果把C放在一个其中一个圆A的圆周上，则圆C的圆周会穿过点A。

假设已得到题目的一个解圆O，则把得到的圆O通过移动，总可以让圆内的某个点X靠在圆周上，换言之，O也在X所作单位圆的圆周上。

由此，可枚举在最终结果的圆周上的点X，目标圆心O在X的圆周上。

每枚举一个X作为图中的点A，枚举其他所有点作为点B，可得到C对应点A、B的在A圆周上的一个范围，覆盖次数最多的那个范围就是当X作为点O圆周上的点所能得到的最优解O的范围，这个次数加1（点X）就是对应X的最优解。

通过枚举所有X，更新出最优解。

覆盖范围可以用圆周角表示，则为区间覆盖问题。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #include<math.h>
 5 #include<algorithm>
 6 const int maxn = 2111;
 7 const double eps = 1e-8;
 8 const double pi = acos(-1.0);
 9 int n, R, ctp;
10 inline int dcmp(double x) {return (x > eps) - (x < -eps);}
11 inline double Sqr(double x){return x * x;}
12 struct Point {int x, y;} p[maxn];
13 inline double CalDis(const Point &a, const Point &b)
14 {return sqrt(Sqr(a.x - b.x) + Sqr(a.y - b.y));}
15 struct Cov { double site; int se;}cover[maxn <<2];
16 int AScomp(const void *a, const void *b)//角度区间排序
17 {
18     if(!dcmp((*(Cov*)a).site - (*(Cov*)b).site))
19         return -((*(Cov*)a).se - (*(Cov*)b).se);
20     return dcmp((*(Cov*)a).site - (*(Cov*)b).site);
21 }
22 void AngManage(double &x)//角度区间修正，(-pi, pi]
23 {
24     while(x + pi < eps) x += 2 * pi;
25     while(x - pi > eps) x -= 2 * pi;
26 }
27 void AddAnSeg(double start, double end)//圆心角转区间
28 {
29     AngManage(start), AngManage(end);
30     if(start - end > eps) AddAnSeg(start, pi), AddAnSeg(-pi + eps * 2, end);
31     else
32     {
33         cover[ctp].site = start, cover[ctp].se = 1;++ ctp;
34         cover[ctp].site = end, cover[ctp].se = -1;++ ctp;
35     }
36 }
37 int MakeAns()
38 {
39     int i, j, ans = 0, cnt;
40     double dis, ang, ac, RR = 2 * (R + 0.001);
41     for(i = 0 ; i < n; ++ i)
42     {
43         for(j = ctp = 0; j < n; ++ j)
44             if(j != i && (dis = CalDis(p[i], p[j])) < RR)
45             {
46                 ang = atan2((double)p[j].y - p[i].y, (double)p[j].x - p[i].x);
47                 ac = acos(dis * 0.5 / R);
48                 AddAnSeg(ang - ac, ang + ac);
49             }
50         qsort(cover, ctp, sizeof(Cov), AScomp);
51         for(j = cnt = 0; j < ctp; ++ j)
52             ans = std::max(ans, cnt += cover[j].se);
53     }
54     return ans + 1;
55 }
56 int main()
57 {
58     while(scanf("%d%d", &n, &R), n | R)
59     {
60         for(int i = 0; i < n; ++ i)
61             scanf("%d%d", &p[i].x, &p[i].y);
62         printf("It is possible to cover %d points.\n", MakeAns());
63     }
64     return 0;
65 }