牛客多校 - Boundary(几何)

题目链接：点击查看

题目大意：给出 n 个点，需要我们选择一个经过原点的圆，使得这个圆经过尽可能多的点，输出最多可以经过多少个点

题目分析：n 的大小是 2000 ，显然支持 n * n 最多再加一个 log 的写法，因为三个不共线的点确定一个圆，圆上的一个点（原点）已经确定了，所以我们可以 O( n ) 枚举一下另一个定点 P，此时大概是这个样子

最后 O( n ) 枚举点 A 时，此时不共线的三点已经可以确定一个圆了，换句话说，三个点就可以确定下来圆心的位置了，当点 P 和点 O 都确定下来后，枚举点 A 所得到的所有圆心的众数再加一，就是以此圆心做圆后可以经过的点的个数，利用map维护最大值就是答案了，找圆心的任务直接交给模板就好了

最后替出题人稍微解释一下吧，并没有卡 double 的精度，如果代码只过了 90% 或 95% 的样例的话，不妨看看下面两个特判：

1
1 0
ans=1

3
1 0
2 0
3 0
ans=1 

代码：
 

#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
using namespace std;
 
typedef long long LL;
 
typedef unsigned long long ull;
 
const int inf=0x3f3f3f3f;
 
const int N=2e3+100;
 
const double eps = 1e-6;
 
int sgn(double x){
    if(fabs(x) < eps)return 0;
    if(x < 0)return -1;
    else return 1;
}
 
struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y){
        x = _x;
        y = _y;
    }
    void input(){
        scanf("%lf%lf",&x,&y);
    }
    bool operator == (Point b)const{
        return sgn(x-b.x) == 0 && sgn(y-b.y) == 0;
    }
    bool operator < (Point b)const{
        return sgn(x-b.x)== 0?sgn(y-b.y)<0:x<b.x;
    }
    Point operator -(const Point &b)const{
        return Point(x-b.x,y-b.y);
    }
    //叉积
    double operator ^(const Point &b)const{
        return x*b.y - y*b.x;
    }
    //返回两点的距离
    double distance(Point p){
        return hypot(x-p.x,y-p.y);
    }
    Point operator +(const Point &b)const{
        return Point(x+b.x,y+b.y);
    }
    Point operator /(const double &k)const{
        return Point(x/k,y/k);
    }
    //`逆时针旋转90度`
    Point rotleft(){
        return Point(-y,x);
    }
}point[N];
 
struct Line{
    Point s,e;
    Line(){}
    Line(Point _s,Point _e){
        s = _s;
        e = _e;
    }
    //`两向量平行(对应直线平行或重合)`
    bool parallel(Line v){
        return sgn((e-s)^(v.e-v.s)) == 0;
    }
    //`求两直线的交点`
    //`要保证两直线不平行或重合`
    Point crosspoint(Line v){
        double a1 = (v.e-v.s)^(s-v.s);
        double a2 = (v.e-v.s)^(e-v.s);
        return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
    }
};
//圆
struct circle{
    Point p;//圆心
    double r;//半径
    circle(){}
    //`三角形的外接圆`
    //`需要Point的+ /  rotate()  以及Line的crosspoint()`
    //`利用两条边的中垂线得到圆心`
    //`测试：UVA12304`
    circle(Point a,Point b,Point c){
        Line u = Line((a+b)/2,((a+b)/2)+((b-a).rotleft()));
        Line v = Line((b+c)/2,((b+c)/2)+((c-b).rotleft()));
        p = u.crosspoint(v);
        r = p.distance(a);
    }
};
 
int main()
{
#ifndef ONLINE_JUDGE
//  freopen("input.txt","r",stdin);
//  freopen("output.txt","w",stdout);
#endif
//  ios::sync_with_stdio(false);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        point[i].input();
    if(n<=1)
        return 0*printf("%d\n",n);
    int ans=1;
    for(int i=1;i<=n;i++)
    {
        map<Point,int>cnt;
        for(int j=i+1;j<=n;j++)
        {
            if(Line(point[i],point[j]).parallel(Line(point[i],Point(0,0))))
                continue;
            circle c(point[i],point[j],Point(0,0));
            ans=max(ans,++cnt[c.p]+1);
        }
    }
    printf("%d\n",ans);
 
 
 
 
 
 
 
    return 0;
}