POJ 1106 Transmitters(计算几何)

题目链接

切计算几何,感觉计算几何的算法还不熟。此题,枚举线段和圆点的直线,平分一个圆

 #include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
#define eps 1e-8
struct point
{
double x,y;
}p[];
double dis(point p1,point p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double xmult(point p1,point p2,point p0)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int main()
{
point r;
double d;
int n,m,i,j,ans,temp;
while(scanf("%lf%lf%lf",&r.x,&r.y,&d)!=EOF)
{
if(d < ) break;
scanf("%d",&n);
m = ;
for(i = ;i < n;i ++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
}
for(i = ;i < n;i ++)
{
if(dis(p[i],r) > d)
continue;
p[m++] = p[i];
}
ans = ;
for(i = ;i < m;i ++)
{
temp = ;
for(j = ;j < m;j ++)
{
if(xmult(p[i],p[j],r) >= )
temp ++;
}
ans = max(ans,temp);
}
printf("%d\n",ans);
}
return ;
}

上一篇:java 7中文件的复制移动


下一篇:PHP验证码类