> #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 代码 求圆上的弧并按直线上线段并写也能对？圆上可能有首尾相接的情况啊，求牛们解释啊。。。

你贴的这份代码并不是按直线上求线段交（不“线段并”）写的。注意代码里有一句 
if(th<0) th+=2*pi;
正是用来处理你所谓的“收尾相接”的情况的。

• 能区分另外一个圆相对圆心A的角度的正负确实保证了这块圆弧计算答案时的正确性 (472) guanjinquan 2021-02-20 21:24:36