poj1981Circle and Points(单位圆覆盖最多的点)

链接

O(n^3)的做法:

枚举任意两点为弦的圆,然后再枚举其它点是否在圆内。

用到了两个函数

atan2反正切函数,据说可以很好的避免一些特殊情况

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 310
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
struct point
{
double x,y;
point(double x = ,double y = ):x(x),y(y){}
}p[N];
double dis(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
point getcircle(point p1,point p2)
{
point mid = point((p1.x+p2.x)/,(p2.y+p1.y)/);
double angle = atan2(p2.y-p1.y,p2.x-p1.x);
double d = sqrt(1.0-dis(p1,mid)*dis(p1,mid));
return point(mid.x+d*sin(angle),mid.y-d*cos(angle));
}
int dcmp(double x)
{
if(fabs(x)<eps)return ;
else return x<?-:;
}
int main()
{
int i,j,n;
while(scanf("%d",&n)&&n)
{
for(i = ;i <= n; i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
int maxz = ;
for(i = ; i <= n; i++)
for(j = i+ ; j <= n ;j++)
{
if(dis(p[i],p[j])>2.0) continue;
int tmax = ;
point cir = getcircle(p[i],p[j]);
for(int g = ; g <= n ;g++)
{
if(dcmp(dis(cir,p[g])-1.0)>)
continue;
tmax++;
}
maxz = max(maxz,tmax);
}
printf("%d\n",maxz);
}
return ;
}

O(n^2log(n))

这个类似扫描线的做法,以每一个点为圆心化圆,枚举与其相交得圆,保存交点和角度,按角度排序后,扫一遍。

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 310
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
struct point
{
double x,y;
point(double x = ,double y = ):x(x),y(y) {}
} p[N];
struct node
{
double ang;
int in;
} arc[N*N];
double dis(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int dcmp(double x)
{
if(fabs(x)<eps)return ;
else return x<?-:;
}
bool cmp(node a,node b)
{
if(dcmp(a.ang-b.ang)==)
return a.in>b.in;
return dcmp(a.ang-b.ang)<;
}
int main()
{
int i,j,n;
while(scanf("%d",&n)&&n)
{
for(i = ; i <= n; i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
int g = ;
int ans = ,maxz = ;
for(i = ; i <= n ; i++)
{
ans = ;
g = ;
for(j = ; j <= n ; j++)
{
if(dis(p[i],p[j])>2.0) continue;
double ang1 = atan2(p[j].y-p[i].y,p[j].x-p[i].x);
double ang2 = acos(dis(p[i],p[j])/);
arc[++g].ang = ang1-ang2;//这里角度的算法很巧妙
arc[g].in = ;
arc[++g].ang = ang1+ang2;
arc[g].in = -;
}
sort(arc+,arc+g+,cmp); //cout<<g<<endl;
for(j = ; j <= g;j++)
{
ans+=arc[j].in;
maxz = max(maxz,ans);
}
}
printf("%d\n",maxz);
}
return ;
}
上一篇:干货云集 WOT 2017全球架构与运维技术峰会揭密技术难点


下一篇:phpcms使用细节