Finding Lines

题目链接：https://codeforces.ml/gym/296012

题意：给你n个点(n<=100000)，问你是否有p%个点在一条直线上(20<=p<=100)。

思路：O(n²)暴力肯定会超时，也想不出其他方法可以做出来。看了题解才知道可以先随机两个点。

因为p >= 20,那么如果要达到目标的话，这条线上至少有n/5个点，那么我们现在来选一对点，选中一个的概率1/5,

两个就是1/25，相应的选不中的概率就是24/25,那么我们随机选取两个点，循环一个较多的次数（1000足矣），

那么，如果答案存在的话，我们选不中的概率就非常非常小了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
struct node
{
    ll x,y;
}a[200005];
int main()
{
    //srand(time(NULL));
    random_device rd;
    int n,p;
    cin>>n>>p;
    p*=n;
    if(p%100)
        p=p/100+1;
    else
        p=p/100;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;
    if(n<=2)
    {
        cout<<"possible"<<endl;
        return 0;
    }
    for(int sj=1;sj<=1000;sj++)
    {

        int x=rd()%n+1;
        int y;
        while(1){
            y=rd()%n+1;
            if(x!=y)
                break;
        }
        int w=2;
        for(int i=1;i<=n;i++)
        {
            if(i==x||i==y)
                continue;
            if((a[y].y-a[x].y)*(a[y].x-a[i].x)==(a[y].y-a[i].y)*(a[y].x-a[x].x))
                w++;
        }
        if(w>=p)
        {
            cout<<"possible"<<endl;
            return 0;
        }
    }
    cout<<"impossible"<<endl;
}