【POJ 1981 】Circle and Points

当两个点距离小于直径时,由它们为弦确定的一个单位圆(虽然有两个圆,但是想一想知道只算一个就可以)来计算覆盖多少点。

#include <cstdio>
#include <cmath>
#define N 301
#define eps 1e-5
using namespace std;
int n,ans,tol;
double x[N],y[N],dx,dy;
inline double sqr(double x)
{
return x*x;
}
inline double dis(int a,int b)
{
return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
inline void solve()
{
tol=;
for(int i=; i<=n; i++)
if(dis(,i)<=+eps)
tol++;
if(tol>ans)ans=tol;
}
inline void get(int a,int b){
double v=atan((x[b]-x[a])/(y[a]-y[b]));//等于0时会返回inf,v=pi/2
double c=sqrt(-sqr(dis(a,b)/2.0));
dx= c*cos(v);
dy= c*sin(v);
}
int main()
{
while(scanf("%d",&n)&&n)
{
ans=;
for (int i=; i<=n; i++)
scanf("%lf%lf",&x[i],&y[i]);
for (int i=; i<=n; i++)
for (int j=i+; j<=n; j++)
if(dis(i,j)<){
double mx=(x[i]+x[j])/2.0,my=(y[i]+y[j])/2.0;
get(i,j);
x[]=mx+dx,y[]=my+dy;
solve();
}
printf("%d\n",ans);
}
}
  
上一篇:SOA架构有基本的要求


下一篇:修改linux swap空间的swappiness,降低对硬盘的缓存