2020牛客暑假多校第二场 B Boundary (数学/map+三点共圆圆心公式)
Boundary
https://ac.nowcoder.com/acm/contest/5667/B
题目大意：
二维平面坐标系，给出很多无序的点，然后求出一个必过（0，0）点且边界上点最多的一个圆。
思路：
因为平面中三点确定一个圆，所以可以枚举两个点，用这两个点和原点确定圆心，这两点和原点不能关于原点对称-->否则圆心就是原点了，不在圆边界上，mp[圆心]++，然后最大值即为答案（要+1因为要加上原点）。
Code：
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn = 2e6+7;
const int mod=1e9+7;
int n,m,k,ans;
struct node{
double x,y;
}p[maxn];
map<pair<double,double>,int> mp;
void solve(node a,node b,node c){ //三点求圆心公式
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));
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));
mp[{x,y}]++;
ans=max(ans,mp[{x,y}]);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>p[i].x>>p[i].y;
}
p[0].x=0.0; p[0].y=0.0; ans=0;
for(int i=1;i<=n;i++){
mp.clear();
for(int j=i+1;j<=n;j++){
if(p[i].x*p[j].y==p[i].y*p[j].x) continue; //不能关于原点对称
solve(p[0],p[i],p[j]);
}
}
cout<<ans+1<<endl;
return 0;
}
查看5道真题和解析