首页 > 代码库 > poj1981Circle and Points(单位圆覆盖最多的点)
poj1981Circle and Points(单位圆覆盖最多的点)
链接
O(n^3)的做法:
枚举任意两点为弦的圆,然后再枚举其它点是否在圆内。
用到了两个函数
atan2反正切函数,据说可以很好的避免一些特殊情况
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set>10 using namespace std;11 #define N 31012 #define LL long long13 #define INF 0xfffffff14 const double eps = 1e-8;15 const double pi = acos(-1.0);16 const double inf = ~0u>>2;17 struct point18 {19 double x,y;20 point(double x = 0,double y =0 ):x(x),y(y){}21 }p[N];22 double dis(point a,point b)23 {24 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));25 }26 point getcircle(point p1,point p2)27 {28 point mid = point((p1.x+p2.x)/2,(p2.y+p1.y)/2);29 double angle = atan2(p2.y-p1.y,p2.x-p1.x);30 double d = sqrt(1.0-dis(p1,mid)*dis(p1,mid));31 return point(mid.x+d*sin(angle),mid.y-d*cos(angle));32 }33 int dcmp(double x)34 {35 if(fabs(x)<eps)return 0;36 else return x<0?-1:1;37 }38 int main()39 {40 int i,j,n;41 while(scanf("%d",&n)&&n)42 {43 for(i = 1 ;i <= n; i++)44 scanf("%lf%lf",&p[i].x,&p[i].y);45 int maxz = 1;46 for(i = 1; i <= n; i++)47 for(j = i+1 ; j <= n ;j++)48 {49 if(dis(p[i],p[j])>2.0) continue;50 int tmax = 0;51 point cir = getcircle(p[i],p[j]);52 for(int g = 1; g <= n ;g++)53 {54 if(dcmp(dis(cir,p[g])-1.0)>0)55 continue;56 tmax++;57 }58 maxz = max(maxz,tmax);59 }60 printf("%d\n",maxz);61 }62 return 0;63 }
O(n^2log(n))
这个类似扫描线的做法,以每一个点为圆心化圆,枚举与其相交得圆,保存交点和角度,按角度排序后,扫一遍。
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set>10 using namespace std;11 #define N 31012 #define LL long long13 #define INF 0xfffffff14 const double eps = 1e-8;15 const double pi = acos(-1.0);16 const double inf = ~0u>>2;17 struct point18 {19 double x,y;20 point(double x = 0,double y =0 ):x(x),y(y) {}21 } p[N];22 struct node23 {24 double ang;25 int in;26 } arc[N*N];27 double dis(point a,point b)28 {29 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));30 }31 int dcmp(double x)32 {33 if(fabs(x)<eps)return 0;34 else return x<0?-1:1;35 }36 bool cmp(node a,node b)37 {38 if(dcmp(a.ang-b.ang)==0)39 return a.in>b.in;40 return dcmp(a.ang-b.ang)<0;41 }42 int main()43 {44 int i,j,n;45 while(scanf("%d",&n)&&n)46 {47 for(i = 1 ; i <= n; i++)48 scanf("%lf%lf",&p[i].x,&p[i].y);49 int g = 0;50 int ans = 0,maxz = 1;51 for(i = 1; i <= n ; i++)52 {53 ans = 0;54 g = 0;55 for(j = 1; j <= n ; j++)56 {57 if(dis(p[i],p[j])>2.0) continue;58 double ang1 = atan2(p[j].y-p[i].y,p[j].x-p[i].x);59 double ang2 = acos(dis(p[i],p[j])/2);60 arc[++g].ang = ang1-ang2;//这里角度的算法很巧妙61 arc[g].in = 1;62 arc[++g].ang = ang1+ang2;63 arc[g].in = -1;64 }65 sort(arc+1,arc+g+1,cmp);66 67 //cout<<g<<endl;68 for(j = 1 ; j <= g;j++)69 {70 ans+=arc[j].in;71 maxz = max(maxz,ans);72 }73 }74 printf("%d\n",maxz);75 }76 return 0;77 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。