Finding Lines UVALive 6955(rand随机化过题 )

本文主要是介绍Finding Lines UVALive 6955(rand随机化过题 )，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给 n（10^5）个点，问是否满足超过%p的点在同一条直线上。 

#include <bits/stdc++.h>
using namespace std;
int x[101000],y[101000];
using namespace std;
bool judge(int a, int b, int c)//判断三点是否共线
{return (y[b] - y[a]) * (x[c] - x[a]) == (y[c] - y[a]) * (x[b] - x[a]);
}
int main()
{int n;int p;while(~scanf("%d%d", &n, &p)){int num = n * p;for(int i = 0; i < n; i++){scanf("%d%d", &x[i],&y[i]);}if(n <= 2){printf("possible\n");continue;}srand(time(0));int flag = 0;for(int i = 0; i < 10000; i++)//随机次数{int u = rand()%n;//枚举点的下标int v = rand()%n;while( u == v) v = rand()%n;//枚举的点不能相同int cnt = 2;//起始枚举的两个点for(int j = 0; j < n; j++)if(j != u && j != v && judge(j,u,v)) cnt++;if(cnt*100>= num){ flag = 1;break;}}if(flag)printf("possible\n");elseprintf("impossible\n");}
}

这篇关于Finding Lines UVALive 6955(rand随机化过题 )的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---