hdu 1883 Phone Cell

http://acm.hdu.edu.cn/showproblem.php?pid=1883

转载:

给出平面上N个点,问一个单位圆最多能覆盖多少个点。

方法一:O(n^3),枚举两个点,确定过这两个点的两个圆的的圆心,循环N个点看有多少个点在这个圆里。

View Code
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<cstdlib>
 5 using namespace std;
 6 const int MAX=2010;
 7 struct node
 8 {
 9     int x,y;
10 }dot[MAX];
11 int n;
12 double r; 
13 double dis(double x1,double y1,double x2,double y2)
14 {
15     return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
16 }
17 void center(double x1,double y1,double x2,double y2,double r,double &a,double &b,int tar)
18 {
19     double px,py;
20     px=x1-x2;
21     py=y1-y2;
22     double midx,midy;
23     midx=(x1+x2)/2.0;
24     midy=(y1+y2)/2.0;
25     double d=dis(midx,midy,x1,y1);
26     double gao=sqrt(r*r-d*d);
27     if (fabs(py)<1e-8  )
28     {
29         if (tar)
30         {
31          a=midx;
32          b=midy+gao;
33         }
34         else 
35         {
36             a=midx;
37             b=midy-gao;
38         }
39     }
40     else
41     {
42         double jiao=atan(-px/py);
43         if (tar)
44         {
45         a=midx+gao*cos(jiao);
46         b=midy+gao*sin(jiao);
47         }
48         else 
49         {
50             a=midx-gao*cos(jiao);
51             b=midy-gao*sin(jiao);
52         }
53     }
54 }
55 int check(double rx,double ry)
56 {
57     int ans=0;
58     for (int i=1;i<=n;i++)
59     {
60         if (dis(rx,ry,dot[i].x,dot[i].y)<r+.001)
61         ans++;    
62     }
63     return ans;
64 }
65 int main()
66 {
67 
68     freopen("D:\in.txt","r",stdin);
69     while (~scanf("%d%lf",&n,&r))
70     {
71         if (n==0) break; 
72         for (int i=1;i<=n;i++)
73         {
74             scanf("%lf%lf",&dot[i].x,&dot[i].y);
75          
76         }
77         int ans=1;
78         for (int i=1;i<=n;i++)
79         {
80             for (int j=i+1;j<=n;j++)
81             {
82                 if (dis(dot[i].x,dot[i].y,dot[j].x,dot[j].y)>r*2) continue;
83                
84                     double rx,ry;
85                     center(dot[i].x,dot[i].y,dot[j].x,dot[j].y,r,rx,ry,0);
86                     int tt=check(rx,ry);
87                     if (tt>ans) ans=tt;
88                     if (ans>=n) break; 
89                
90             }
91         }
92         printf("It is possible to cover %d points.\n",ans);
93         
94     }
95     return 0;
96 }

方法一TLE;

方法二:O(n^2logn),首先需要挖掘出来:如果一段圆弧被某个单位圆C覆盖过,那么我们把目标单位圆A的圆心放在该段弧上时,目标圆A一定能把C的圆心覆盖,也能把圆弧所在的圆B的圆心覆盖。

所以,被覆盖次数最多的弧的被覆盖次数即为目标圆最多能够覆盖的点数。

做法:

1.首先枚举一个点作为圆心A,然后再循环其它N-1个点,设当前循环到的点为B。

2.用atan2函数求直线BA的极角th,为方便极角排序,对于负角要+2pi。

3.求圆A,B的交点与AB的夹角ph=acos(D/2),D=dist(A,B)。

4.计算圆B覆盖圆A的弧的始末极角th-ph+2pi和th+ph+2pi,为了避免负角,每个极角均加2pi。同时加上标记区分始末点。

5.对这2*n个始末点排序,扫描一遍,得到覆盖次数最多的弧的被覆盖次数,更新答案。

View Code
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<iostream> 
 5 #include<algorithm>
 6 #include<cmath>
 7 using namespace std;
 8 const double eps=1e-8;
 9 const int N=2100;
10 const double pi=acos(-1.0); 
11 struct Point 
12 {
13     double x,y; 
14     void input()
15     {
16         scanf("%lf%lf",&x,&y); 
17     } 
18 }point[N];
19 
20 int n;
21 double r;
22 struct node 
23 {
24     double angle;
25     int flag; 
26 }que[N*2+10];
27 inline int dcmp(double d) {
28     return d < -eps ? -1 : d > eps;
29 }
30 
31 bool cmp(const node &a,const node &b)
32 {
33     if (dcmp(a.angle-b.angle)==0) return a.flag>b.flag;
34     return a.angle<b.angle; 
35 }
36 double sqr(double x)
37 {
38     return x*x; 
39 } 
40 double dis(const Point &a,const Point &b)
41 {
42     return sqrt(sqr(a.x - b.x)+sqr(a.y - b.y)); 
43 } 
44 int main()
45 {    
46     freopen("D:\in.txt","r",stdin); 
47     while (~scanf("%d%lf",&n,&r))
48     {
49         if (n==0) break;
50         for (int i=0;i<n;i++) point[i].input(); 
51         int ans=0; 
52         
53         for (int i=0;i<n;i++)
54         {
55             int sz=0; 
56             for (int j=0;j<n;j++)
57             {
58                 if (i==j) continue;
59                 double d=dis(point[i],point[j]);
60                 if (d>2*r+0.001) continue;
61                 double th=atan2(point[j].y-point[i].y,point[j].x-point[i].x) ; 
62                 if (th<0) th+=2*pi; 
63                 double ph=acos(d/2.0/r);
64                 que[sz++].angle=th-ph+2*pi;que[sz-1].flag=1;
65                  que[sz++].angle=th+ph+2*pi;que[sz-1].flag=-1;
66             }    
67             sort(que,que+sz,cmp);
68             int sum=0; 
69             for (int j=0;j<sz;j++) ans=max(ans,sum+=que[j].flag);        
70         } 
71         printf("It is possible to cover %d points.\n", ans+1);
72     } 
73     return 0; 
74 } 
原文地址:https://www.cnblogs.com/Rlemon/p/2625858.html