（Uva 6955可以直接随机，湖大OJ 13348 要优化）
题意：给出 n个点的坐标， 一个 百分数p， 求是否有一条直线上有 n * p /100个点…
随机化算法，但也要优化下……（TLE， WA到底…）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<stack>
//#include<bits/std c++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const LL MOD = 1e7 + ;
const LL maxn = 1e5 + ;
int gcd(int a,int b) { return b == ? a : gcd(b, a % b); }
unsigned int Rand() { static unsigned seed = ; return seed = seed * + ;}
struct Line {
long long a,b,c;
Line() {}
Line(int a1,int b1,int a2,int b2) {
int g = gcd(abs(a1 - a2),abs(b1 - b2));
if(a1 - a2 < ) g = -g;
a = -(b1-b2)/g;
b = (a1-a2) / g;
c = a*a1 + b*b1;
}
bool operator < (Line s) const { return (a < s.a || (a == s.a && (b < s.b || (b == s.b && c < s.c))));}
};
map<Line,int> L;
map<Line,int>::iterator it;
int X[], Y[];
int main() {
int n,p;
scanf("%d%d",&n,&p);
L.clear();
if(n == ) {
printf("possible\n");
return ;}
int limit = n * p;
for(int i = ; i < n; ++i) scanf("%d%d",&X[i],&Y[i]);
for(int t = ; t < ; ++t) { //先随机处理去重 + 统计次数
int a = Rand() % n, b = Rand() % n;
while(a == b) b = Rand() % n;
L[Line(X[a],Y[a],X[b],Y[b])]++;
}
for(it = L.begin(); it != L.end(); ++it)
{
if(it->second < ) continue;//随机1000次，在线上的点应该要出现一定次数 1/25 * 1000， 20保险，然而30 40 WA了...
int num = ; //简直拼人品.......
long long a = it->first.a, b = it->first.b, c = it->first.c;
for(int i = ; i < n; ++i) {
if(a*X[i] + b*Y[i] == c) {
num++;
if(num * >= limit) {
printf("possible\n");
return ;
}
}
}
}
printf("impossible\n");
return ;
}