2020牛客暑期多校（第二场）B

题目描述

  Given points in plane. Considering all circles that the origin point is on their boundries, find the one with the maximum given points on its boundry. Print the maximum number of points.

输入描述

  The first line contains one integer , denoting the number of given points.
  Following lines each contains two integers , denoting a given point .
  It's guaranteed that the points are pairwise different and no given point is the origin point.

输出描述

  Only one line containing one integer, denoting the answer.

示例1

输入

4  
1 1  
0 2  
2 0  
2 2

输出

3  

说明

  Considering circle , we can see that the origin point is on its boundry and that there are given points on its boundry.

分析

  不共线的三点确定一个圆，已知其中一个点为 ，可以在 的时间内枚举得到另外两个点，得到不共线的三点后，可以轻易计算出三点所确定的圆心。
  当第一层枚举得到点 ，那么再枚举一个点即可得到圆心，若第三个点 或 同 和原点确定的圆心都为 ，那么 都被同一个圆的边界覆盖。第一层枚举后，用 记录在 边界上的点（第二层枚举得到的点）的个数，取最大即可，因为圆上的点还有第一层枚举得到的点，最大值还要增加 。
  枚举的方式，可保证不重复不遗漏。若枚举点 ，有 都与 在同一个圆上，那么有 个点在同一个圆上；当下一次枚举到 ，第三层枚举不会涉及到 ，可以确定的是，会得到有 与 在同一点上。

for(i=1;i<=n;i++)
{
    for(j=i+1;j<=n;j++)
    {
        \\function
    }
}

代码

#include<iostream>
#include<map>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const double eps=1e-6;
const int N=2005;
int n;
struct CPoint 
{
    double x;
    double y;
    bool operator<(const CPoint& A)const
    {
        if(x==A.x) return A.y-y>eps;
        else return A.x-x>eps;
    }
}p[N];
map<CPoint,int>cnt;
int main()
{
    cin>>n;
    int i,j;
    for(i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
    int ans=1;//至少能覆盖一个点
    for(i=1;i<=n;i++)
    {
        cnt.clear();
        for(j=i+1;j<=n;j++)
        {
        //===========================================
        //三点确定圆心模板
            double x1=0,y1=0;
            double x2=p[i].x,y2=p[i].y;
            double x3=p[j].x,y3=p[j].y;
            double a=x1-x2;
            double b=y1-y2;
            double c=x1-x3;
            double d=y1-y3;
            double e=((x1*x1-x2*x2)-(y2*y2-y1*y1))/2;
            double f=((x1*x1-x3*x3)+(y1*y1-y3*y3))/2;
            if(fabs(b*c-a*d)<eps) continue;
            CPoint C;//圆心
            C.x=(b*f-d*e)/(b*c-a*d);
            C.y=(c*e-a*f)/(b*c-a*d);
        //============================================
            cnt[C]++;//j1,j2,...,jk
        }
        //+1 囊括第一层枚举的点
        for(auto v:cnt) ans=max(ans,v.second+1);
    }
    cout<<ans<<endl;
    return 0;
}