2020牛客多校(第二场) B. Boundary (计算几何)

Description
Given ${n}$n points in 2D plane. Considering all circles that the origin point ${(0, 0)}$(0,0) is on their boundries, find the one with the maximum given points on its boundry. Print the maximum number of points.

Input
The first line contains one integer $n~(1 \leq n \leq 2000)$n (1≤n≤2000), denoting the number of given points.
Following $n$n lines each contains two integers $x, y~(|x|,|y| \leq 10000)$x,y (∣x∣,∣y∣≤10000), denoting a given point $(x,y)$(x,y).
It’s guaranteed that the points are pairwise different and no given point is the origin point

Output
Only one line containing one integer, denoting the answer.

Examples

Input
4
1 1
0 2
2 0
2 2

Output
3

Note
Considering circle $(x-1)^2+(y-1)^2 =2$(x−1)2+(y−1)2=2, we can see that the origin point is on its boundry and that there are 3 given points$(0,2),(2,0),(2,2)$(0,2),(2,0),(2,2) on its boundry.

Solution
最优解的圆肯定覆盖了至少两个点，所以我们枚举两个点和原点组成的圆的圆心，再用map统计答案

Code

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-6;
const int maxn = 4e3 + 7;
struct Point{
    double x,y;
    Point(double _x=0,double _y=0){
        x=_x;
        y=_y;
    }
    void read(){
        scanf("%lf %lf",&x,&y);
    }
    Point operator-(const Point& p1)const{return Point(x-p1.x,y-p1.y);}
    Point operator+(const Point& p1)const{return Point(x+p1.x,y+p1.y);}
    bool friend operator<(const Point& p1,const Point& p2){
        if(fabs(p1.x-p2.x)>eps)return p1.x<p2.x;return p1.y<p2.y;
    }
    bool friend operator==(const Point& p1,const Point& p2){
        if(fabs(p1.x-p2.x)>eps)return 0;
        if(fabs(p1.y-p2.y)>eps)return 0;
        return 1;
    }
    double friend operator^(const Point& p1,const Point& p2){return p1.x*p2.y-p2.x*p1.y;}
    Point friend operator*(const Point& p1,const double& k){return Point(p1.x*k,p1.y*k);}
    double friend operator*(const Point& p1,const Point& p2){return p1.x*p2.x+p1.y*p2.y;}
}a[maxn];

map<Point,int>mp;

Point GetCenter(const Point& p1,const Point& p2,const Point& p3){
    Point cp;
    double a1=p2.x-p1.x,b1=p2.y-p1.y,c1=(a1*a1+b1*b1)/2;
    double a2=p3.x-p1.x,b2=p3.y-p1.y,c2=(a2*a2+b2*b2)/2;
    double d=a1*b2-a2*b1;
    cp.x=p1.x+(c1*b2-c2*b1)/d;
    cp.y=p1.y+(a1*c2-a2*c1)/d;
    return cp;
}

int main(){
    int res = 0,n;scanf("%d",&n);
    for(int i = 1;i <= n;++i){
        a[i].read();
    }
    if(n <= 2) {printf("%d\n",n);return 0;}
    for(int i = 1;i <= n;++i){
        mp.clear();
        for(int j = i + 1;j <= n;++j){
            if(fabs(a[i] ^ a[j]) < eps) continue;
            Point p = GetCenter(Point(0,0),a[i],a[j]);
            mp[p]++;
            res = max(res,mp[p]);
        }
    }
    printf("%d\n", res + 1);
    return 0;
}