欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Boundary

程序员文章站 2022-03-02 10:55:00
...

题目:Boundary
已知三点,求圆心、半径
x=((y2-y1)(y3y3-y1y1+x3x3-x1x1)-(y3-y1)(y2y2-y1y1+x2x2-x1x1))/(2.0*((x3-x1)(y2-y1)-(x2-x1)(y3-y1)));
y=((x2-x1)(x3x3-x1x1+y3y3-y1y1)-(x3-x1)(x2x2-x1x1+y2y2-y1y1))/(2.0*((y3-y1)(x2-x1)-(y2-y1)(x3-x1)));
r=(x1-x)(x1-x+(y1-y)(y1-y);

题解:三点可以求一个圆心,那么根据两个点,求出圆心,看哪个点最多。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lf;
typedef pair<lf,lf>P;
const int inf = 0x7f7f7f7f;
const int N = 2e5+10;
const ll mod = 998244353;
const double PI = 3.14;

int read(){
    char ch=getchar();int x=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int random(int n){return(ll)rand()*rand()%n;}

lf x[N],y[N];
map<P,int> mp;

int main(){
    int n = read();
    for(int i = 1;i <= n;i++){
        cin >> x[i] >> y[i];
    }
    int ans = 0;
    for(int i = 1;i <= n;i++){
        mp.clear();
        for(int j = 1;j <= n;j++){
            if(j == i) continue;
            if(x[j]*y[i]-y[j]*x[i] == 0) continue;//此时三点共线,不成立
            lf xx = ((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]);
			lf yy = ((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]);
            mp[P(xx,yy)]++;
            ans = max(ans,mp[P(xx,yy)]);
        }
    }
    cout<<ans+1<<endl;
    return 0;
}
相关标签: 牛客