#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<double , double>;
int n;
PII p[3000010];
vector<PII> pp;
PII yuan(PII a , PII b , PII c)
{//已知三个点确定圆的半径和圆心double x1 = a.first,x2 = b.first,x3 = c.first,y1 = a.second,y2 = b.second,y3 = c.second,x,y,r,A,B,C,D;A=x1*(y2-y3)-y1*(x2-x3)+x2*y3-x3*y2;B=(x1*x1+y1*y1)*(y3-y2)+(x2*x2+y2*y2)*(y1-y3)+(x3*x3+y3*y3)*(y2-y1);C=(x1*x1+y1*y1)*(x2-x3)+(x2*x2+y2*y2)*(x3-x1)+(x3*x3+y3*y3)*(x1-x2);D=(x1*x1+y1*y1)*(x3*y2-x2*y3)+(x2*x2+y2*y2)*(x1*y3-x3*y1)+(x3*x3+y3*y3)*(x2*y1-x1*y2);x=-B/(2*A);y=-C/(2*A);//r=sqrt((B*B+C*C-4*A*D)/(4*A*A));//-1表示圆不存在if(!A){return {-1e9 , -1e9};}else{return {x,y};}}
int main(){cin>>n;for(int i = 1; i <= n ; i++){cin>>p[i].first>>p[i].second;}for(int i = 1; i <= n ; i++){for(int j = i + 1; j <= n; j++){auto x = yuan({0,0} , p[i] , p[j]);if(x.first == -1e9 && x.second == -1e9) continue;else pp.push_back(x);}}if(pp.size() == 0){cout<<1;return 0;}sort(pp.begin() , pp.end());auto now = pp[0];int num = 1;int ct = 1;//记录每个圆心出现多少次for(int i = 1; i < pp.size() ; i++){if(pp[i] == now) {num++;ct = max(ct, num);}else{now = pp[i];ct = max(ct , num);num = 1;}}for(int i = 1 ; i <= n ; i++){if(i * (i-1) >> 1 == ct){cout<<i;return 0;}}
}
B-Boundary_2023牛客国庆集训派对day2 (nowcoder.com)
圆心的计算公式是抄的 , 然后这题想到枚举圆心很简单,三点定圆
然后就是考虑哪个圆心出现的次数最多,
考虑这个圆心经过了n 个点 那么这个圆心就会出现次 ,
= ct