abc422_e题解

cyq32ent · 2025-09-07 13:41:31 · 题解

随机选取两个点，则这两个点过所求直线的概率，即这两个点在直线经过的点集 S 中的概率。由于我们假定 |S|>\frac N2，所以这个概率不小于 \frac14。进行 50 次测试，则误判的概率为 5.66\times 10^{-7} 左右，如果 50 次测试均不通过，可以认为这不存在这样一条直线。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int N,x[514514],y[514514];
void check(int i,int j){
    int a=y[j]-y[i],b=x[i]-x[j],c=x[j]*y[i]-x[i]*y[j],cnt=0;
    for(int _=1;_<=N;_++)if(a*x[_]+b*y[_]+c==0)cnt++;
    if(cnt>=N/2+1)cout<<"Yes\n"<<a<<' '<<b<<' '<<c,exit(0);
}
signed main(){
    mt19937 rnd(time(0));
    cin>>N;for(int i=1;i<=N;i++)cin>>x[i]>>y[i];
    for(int _=0;_<50;_++){
        int i=rnd()%N+1,j=rnd()%N+1;if(j==i)j=(i)%N+1;
        check(i,j);
    }cout<<"No";
    return 0;
}