2020牛客暑期多校训练营(第二场) Boundary
传送门:Boundary
题意:给你n个点的坐标,问最多有多少个点可以在同一个圆上,(0,0)必须在这个圆上。
题解:三个点确定一个圆,所以暴力枚举两个点和(0,0)组成的圆,如果三个点不共线的话,用圆心公式求出圆心,然后用map记录以当前点为圆心的点圆的个数,边记录边判断有多少个圆圆心是同一个点,取最大值就好了。
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define ft first 5 #define sd second 6 #define pii pair<int,int> 7 #define pll pair<ll,ll> 8 using namespace std; 9 10 const int maxn=2e6+10; 11 12 struct Point{ 13 double x,y; 14 }p[maxn]; 15 16 map<pair<double,double>,int>mp; 17 int ans=0; 18 19 void solve(Point a,Point b,Point c)//三点共圆圆心公式 20 { 21 double x=( (a.x*a.x-b.x*b.x+a.y*a.y-b.y*b.y)*(a.y-c.y)-(a.x*a.x-c.x*c.x+a.y*a.y-c.y*c.y)*(a.y-b.y) ) / (2.0*(a.y-c.y)*(a.x-b.x)-2*(a.y-b.y)*(a.x-c.x)); 22 double y=( (a.x*a.x-b.x*b.x+a.y*a.y-b.y*b.y)*(a.x-c.x)-(a.x*a.x-c.x*c.x+a.y*a.y-c.y*c.y)*(a.x-b.x) ) / (2.0*(a.y-b.y)*(a.x-c.x)-2*(a.y-c.y)*(a.x-b.x)); 23 mp[{x,y}]++; 24 ans=max(ans,mp[{x,y}]); 25 } 26 27 int main() 28 { 29 ios::sync_with_stdio(false); 30 cin.tie(0); 31 cout.tie(0); 32 int n; 33 cin>>n; 34 for(int i=0;i<n;i++){ 35 cin>>p[i].x>>p[i].y; 36 } 37 for(int i=0;i<n;i++){ 38 mp.clear(); 39 for(int j=i+1;j<n;j++){ 40 if(p[i].x*p[j].y==p[i].y*p[j].x) continue; 41 solve({0.0,0.0},p[i],p[j]); 42 } 43 } 44 cout<<ans+1<<endl; 45 return 0; 46 }
PS:因为有人留言问,博主又有了肝的动力(T^T),按照出题人题解ppt的方法写了一下代码,debug了半天,精度确实会有问题,用数组存起来,遍历差值<1e-10的就好了,如果这个小于的值太大的话会过不去的。下边代码里有个地方k==0特判一下才能过,不然有一组数据过不去,个人认为是sort函数不能sort(a,a)这样写,不知道是不是这个地方。
出题人的题解:
代码:
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define ft first 5 #define sd second 6 #define pii pair<int,int> 7 #define pll pair<ll,ll> 8 using namespace std; 9 10 const int maxn=2e6+10; 11 12 struct Point{ 13 double x,y; 14 }p[maxn]; 15 16 double dis(Point x,Point y) 17 { 18 return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y)); 19 } 20 21 double dis2(Point x,Point y) 22 { 23 return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y); 24 } 25 26 double mp[maxn]; 27 int ans=0; 28 29 int main() 30 { 31 ios::sync_with_stdio(false); 32 cin.tie(0); 33 cout.tie(0); 34 int n; 35 cin>>n; 36 if(n==1){ 37 cout<<1<<endl; 38 return 0; 39 } 40 for(int i=0;i<n;i++){ 41 cin>>p[i].x>>p[i].y; 42 } 43 for(int i=0;i<n;i++){ //枚举p 44 int k=0; 45 for(int j=0;j<n;j++){ //枚举A 46 if(p[i].x*p[j].y>=p[i].y*p[j].x) continue; //A在op的左边或者共线,就不要 47 double ap1=dis(p[i],p[j]); 48 double oa1=dis({0.0,0.0},p[j]); 49 double ap2=dis2(p[i],p[j]); 50 double op2=dis2({0.0,0.0},p[i]); 51 double oa2=dis2({0.0,0.0},p[j]); 52 53 double q=(ap2+oa2-op2)/2.0/ap1/oa1; //cos(∠OAP) 54 double angle=acos(q); //∠OAP 55 mp[k++]=angle; 56 } 57 if(k==0) continue; //这个地方没写的话会有一组数据过不去,个人认为是sort(mp,mp)这样会出bug,不知道是不是 58 sort(mp,mp+k); 59 int cnt=1; 60 for(int i=1;i<k;i++){ 61 if(fabs(mp[i]-mp[i-1])<1e-10) cnt++; 62 else cnt=1; 63 ans=max(ans,cnt); 64 } 65 ans=max(ans,cnt); 66 } 67 cout<<ans+1<<endl; 68 return 0; 69 }