Finding Lines

时间:2023-03-09 18:53:14
Finding Lines

Finding Lines

题目链接:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4967

概率

在听题解前毫无头绪,题解帮我打开了新世界的大门:

随机取一个点在答案直线(如果存在这个直线)上的概率是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";
}
}