Finding Lines
概率
在听题解前毫无头绪,题解帮我打开了新世界的大门:
随机取一个点在答案直线(如果存在这个直线)上的概率是p%,
那么随机取到两个点构成的直线就是答案直线的概率是p%*p%;
也就是说,随机取到两个点构成的直线不是答案直线的概率为1-p%*p%<=24/25.
如果我们每次随机取两个点,判定一下这条直线上是否存在p%*n个点,
进行k次后得到错误答案的概率是(1-p%*p%)k.
k取足够大,可以使错误答案的概率趋向于0;当k=100时,错误概率为0.01687.
注意:n<=2时需要特判
代码如下:
#include<iostream>
#include<cstdlib>
#include<ctime>
#define N 100005
using namespace std;
typedef long long ll;
struct point{
ll x,y;
}a[N];
ll n,p,ans;
ll check(ll first,ll second){
ll sum=;
ll x1=a[first].x-a[second].x;
ll y1=a[first].y-a[second].y;
for(int i=;i<n;++i){
if(i==first||i==second)continue;
ll x2=a[i].x-a[second].x;
ll y2=a[i].y-a[second].y;
if(x1*y2-x2*y1==)sum++;
}
if(sum*-p*n>=)return ;
return ;
}
int main(void){
while(cin>>n>>p){
for(ll i=;i<n;++i)
cin>>a[i].x>>a[i].y;
if(n<=){
cout<<"possible\n";
continue;
}
ans=;
srand((int)time());
for(ll t=;t<;++t){
ll first=rand()%n,second=rand()%n;
if(first==second)continue;
ans+=check(first,second);
}
if(ans)cout<<"possible\n";
else cout<<"impossible\n";
}
}