AT_abc422_e

HasNoName · 2025-09-17 14:21:04 · 题解

思路

看到 \frac{n+1}{2}，首先想到随机化。

考虑有一道叫 ghd 的题就是这个方法。

可以考虑任意取两条点连成的线有 \frac{\frac{n+1}{4}\times\frac{n-1}{4}}{\frac{n}{2}\times\frac{n-1}{2}}=\frac{n+1}{4n} 的概率是正确答案。

所以速记两个点多次，每个点 O(N) 判断即可。

出错概率是非常低的。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500005;
struct T
{
    ll x,y;
}p[N];
int n;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y;
    mt19937 rand(31415926);
    for(int i=1;i<=200;i++)
    {
        int x=rand()%n+1,y=rand()%n+1;
        if(x==y)continue;
        ll a,b,c;
        a=-p[x].y+p[y].y;b=p[x].x-p[y].x;//点斜式
        c=-(a*p[x].x+b*p[x].y);
        int cnt=0;
        for(int j=1;j<=n;j++)
            if(a*p[j].x+b*p[j].y+c==0)cnt++;//判断
        if(cnt>n/2)
        {
            cout<<"Yes\n";
            cout<<a<<' '<<b<<' '<<c<<'\n';
            return 0;
        }
    }
    cout<<"No\n";
    return 0;
}