首页 > ACM题库 > HDU-杭电 > HDU 1883 Phone Cell-几何题-[解题报告] C++
2013
12-23

HDU 1883 Phone Cell-几何题-[解题报告] C++

Phone Cell

问题描述 :

Nowadays, everyone has a cellphone, or even two or three. You probably know where their name comes from. Do you? Cellphones can be moved (they are “mobile”) and they use wireless connection to static stations called BTS (Base Transceiver Station). Each BTS covers an area around it and that area is called a cell.

The Czech Technical University runs an experimental private GSM network with a BTS right on top of the building you are in just now. Since the placement of base stations is very important for the network coverage, your task is to create a program that will find the optimal position for a BTS. The program will be given coordinates of “points of interest”.The goal is to find a position that will cover the maximal number of these points. It is supposed that a BTS can cover all points that are no further than some given distance R. Therefore, the cell has a circular shape.

The picture above shows eight points of interest (little circles) and one of the possible optimal BTS positions (small triangle). For the given distance R, it is not possible to cover more than four points. Notice that the BTS does not need to be placed in an existing point of interest.

输入:

The input consists of several scenarios. Each scenario begins with a line containing two integer numbers N and R. N is the number of points of interest, 1 ≤ N ≤ 2000. R is the maximal distance the BTS is able to cover, 0 ≤ R < 10 000. Then there are N lines, each containing two integer numbers Xi , Yi giving coordinates of the i-th point, |Xi|,|Yi| < 10 000. All points are distinct, i.e., no two of them will have the same coordinates.

The scenario is followed by one empty line and then the next scenario begins. The last one is followed by a line containing two zeros.

A point lying at the circle boundary (exactly in the distance R) is considered covered. To avoid floating-point inaccuracies, the input points will be selected in such a way that for any possible subset of points S that can be covered by a circle with the radius R + 0.001, there will always exist a circle with the radius R that also covers them.

输出:

For each scenario, print one line containing the sentence “It is possible to cover M points.”, where M is the maximal number of points of interest that may be covered by a single BTS.

样例输入:

8 2
1 2
5 3
5 4
1 4
8 2
4 5
7 5
3 3

2 100
0 100
0 -100

0 0

样例输出:

It is possible to cover 4 points.
It is possible to cover 2 points.

Hint
The first sample input scenario corresponds to the picture, providing that the X axis aims right and Y axis down.

如上图,设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,更新出最优解。

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

#include<stdio.h>
 #include<string.h>
 #include<stdlib.h>
 #include<math.h>
 #include<algorithm>
 const int maxn = 2111;
 const double eps = 1e-8;
 const double pi = acos(-1.0);
 int n, R, ctp;
 inline int dcmp(double x) {return (x > eps) - (x < -eps);}
 inline double Sqr(double x){return x * x;}
 struct Point {int x, y;} p[maxn];
 inline double CalDis(const Point &a, const Point &b)
 {return sqrt(Sqr(a.x - b.x) + Sqr(a.y - b.y));}
 struct Cov { double site; int se;}cover[maxn <<2];
 int AScomp(const void *a, const void *b)//角度区间排序
 {
     if(!dcmp((*(Cov*)a).site - (*(Cov*)b).site))
         return -((*(Cov*)a).se - (*(Cov*)b).se);
     return dcmp((*(Cov*)a).site - (*(Cov*)b).site);
 }
 void AngManage(double &x)//角度区间修正,(-pi, pi]
 {
     while(x + pi < eps) x += 2 * pi;
     while(x - pi > eps) x -= 2 * pi;
 }
 void AddAnSeg(double start, double end)//圆心角转区间
 {
     AngManage(start), AngManage(end);
     if(start - end > eps) AddAnSeg(start, pi), AddAnSeg(-pi + eps * 2, end);
     else
     {
         cover[ctp].site = start, cover[ctp].se = 1;++ ctp;
         cover[ctp].site = end, cover[ctp].se = -1;++ ctp;
     }
 }
 int MakeAns()
 {
     int i, j, ans = 0, cnt;
     double dis, ang, ac, RR = 2 * (R + 0.001);
     for(i = 0 ; i < n; ++ i)
     {
         for(j = ctp = 0; j < n; ++ j)
             if(j != i && (dis = CalDis(p[i], p[j])) < RR)
             {
                 ang = atan2((double)p[j].y - p[i].y, (double)p[j].x - p[i].x);
                 ac = acos(dis * 0.5 / R);
                 AddAnSeg(ang - ac, ang + ac);
             }
         qsort(cover, ctp, sizeof(Cov), AScomp);
         for(j = cnt = 0; j < ctp; ++ j)
             ans = std::max(ans, cnt += cover[j].se);
     }
     return ans + 1;
 }
 int main()
 {
     while(scanf("%d%d", &n, &R), n | R)
     {
         for(int i = 0; i < n; ++ i)
             scanf("%d%d", &p[i].x, &p[i].y);
         printf("It is possible to cover %d points.\n", MakeAns());
     }
     return 0;
 }

解题报告转自:http://www.cnblogs.com/CSGrandeur/archive/2012/09/10/2678682.html