不是啊。我就想写个傻逼题玩玩。怎么都这么自闭啊。
找个单位圆覆盖最多的点。
n^3显然。然后被卡了。
懒得优化，考虑n^2logn的做法。
地址：https://www.cnblogs.com/weeping/p/7655975.html
相当于对每个角度记录一下贡献然后排个序扫一下。
1 #include <cstdio> 2 #include <cmath> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 typedef double db; 7 const db eps=1e-7; 8 const db pi=acos(-1); 9 int sign(db k){ 10 if (k>eps) return 1; else if (k<-eps) return -1; return 0; 11 } 12 int cmp(db k1,db k2){return sign(k1-k2);} 13 struct point{ 14 db x,y; 15 point operator + (const point &k1) const{return (point){k1.x+x,k1.y+y};} 16 point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};} 17 point operator * (db k1) const{return (point){x*k1,y*k1};} 18 point operator / (db k1) const{return (point){x/k1,y/k1};} 19 db abs(){return sqrt(x*x+y*y);} 20 db abs2(){return x*x+y*y;} 21 db dis(point k1){return ((*this)-k1).abs();} 22 point unit(){db w=abs(); return (point){x/w,y/w};} 23 point turn90(){return (point){-y,x};} 24 bool operator < (const point k1) const{ 25 int a=cmp(x,k1.x); 26 if (a==-1) return 1; else if (a==1) return 0; else return cmp(y,k1.y)==-1; 27 } 28 }; 29 int n;point p[307],l[612]; 30 int main(){ 31 while (scanf("%d",&n)&&n){ 32 for(int i=1;i<=n;i++){ 33 scanf("%lf%lf",&p[i].x,&p[i].y); 34 } 35 if(n==1){ 36 printf("1 "); 37 }else{ 38 int ans = 1; 39 for(int i=1;i<n;i++){ 40 int cnt = 0; 41 for(int j=1;j<=n;j++){ 42 if(i==j)continue; 43 db d = p[i].dis(p[j])/2; 44 if(cmp(d,1)>0)continue; 45 db alf = atan2(p[j].y-p[i].y,p[j].x-p[i].x); 46 db dlt = acos(d); 47 l[cnt++]={alf-dlt,1}; 48 l[cnt++]={alf+dlt,-1}; 49 } 50 sort(l,l+cnt); 51 int res = 1; 52 for(int j=0;j<cnt;j++){ 53 if(cmp(l[j].y,1)==0)res++; 54 else res--; 55 ans=max(ans,res); 56 } 57 } 58 printf("%d ",ans); 59 } 60 } 61 }