#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct rec{double dat;int cov;}c[610];
double a[310],b[310],th,ph,pi=acos(-1.0),dis;
int n,m,i,j,k,ans;
bool cmp(rec a,rec b)
{
return fabs(a.dat-b.dat)<1e-12?a.cov>b.cov:a.dat<b.dat;
}
int main()
{
while(cin>>n&&n)
{
for(i=1;i<=n;i++) scanf("%lf%lf",&a[i],&b[i]);
for(ans=0,i=1;i<n;i++)
{
for(m=0,j=1;j<=n;j++)
{
if(i==j)continue;
dis=sqrt((a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j]));
if(dis>2)continue;
th=atan2(b[j]-b[i],a[j]-a[i]);
if(th<0) th+=2*pi;
ph=acos(dis/2);
c[++m].dat=th-ph+2*pi; c[m].cov=1;
c[++m].dat=th+ph+2*pi; c[m].cov=-1;
}
sort(c+1,c+m+1,cmp);
for(k=0,j=1;j<=m;j++)ans=max(ans,(k+=c[j].cov));
}
cout<<ans+1<<endl;
}
return 0;
}


这是网上的AC的 n*n*logn 代码 求圆上的弧并按直线上线段并写也能对？圆上可能有首尾相接的情况啊，求牛们解释啊。。。

• Re:在圆上求弧并应该比在直线上求线段并复杂吧？怎么这些AC的代码都是按直线上求线段并写的呢？？数据弱了吧 (1017) the_brothers_four 2017-02-09 13:24:52
  • 能区分另外一个圆相对圆心A的角度的正负确实保证了这块圆弧计算答案时的正确性 (472) guanjinquan 2021-02-20 21:24:36