牛客多校2—— Boundary （计算几何）

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

思路：

三点不共线的点确定一个圆 O点已经确定，O（n）枚举另一个点P，O（n）枚举第三个点 ，这样三点就可以确定一个圆心，每次都取圆心出现最多的次数。

注意枚举的时候排除掉三点共线的情况。

代码：

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define I_int ll
typedef pair<int,int> PII;
typedef pair<double,double>PDD;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char F[200];
inline void out(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
    //cout<<" ";
}

const int maxn=500000+100;

double x[maxn],y[maxn];
map<PDD,ll>mp;

int main(){
    int n=read();
    for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);
    ll res=0;
    for(int i=1;i<=n;i++){///枚举点P
        mp.clear();
        for(int j=i+1;j<=n;j++){
            if(x[j]*y[i]-y[j]*x[i]==0) continue; //三点共线
            PDD tmp;
            tmp.first=((y[j]-y[i])*y[i]*y[j]-x[i]*x[i]*y[j]+x[j]*x[j]*y[i])/(x[j]*y[i]-x[i]*y[j]);
            tmp.second= ((x[j]-x[i])*x[i]*x[j]-y[i]*y[i]*x[j]+y[j]*y[j]*x[i])/(y[j]*x[i]-y[i]*x[j]);
            res=max(res,++mp[tmp]);
        }
    }
    out(res+1);
    return 0;
}

参考博客： http://blog.sina.com.cn/s/blog_71726b130101dx6u.html

https://blog.csdn.net/weixin_42868863/article/details/107382515