codechef Milestones

题意:

平面上有n(n<=10000)个点,已知用7条直线就能完全覆盖它们.

求最多用1条直线可以覆盖多少个点

随机1000次就能过了。。。

Portal

#include <time.h>
#include <stdio.h>
#include <stdlib.h> 
#include <string.h>
#include <algorithm>
using namespace std;

#define g() getchar()
template<class Q>void Scan(Q&x){
	char c;int f=1;
	while(c=g(),c<48||c>57)if(c=='-')f=-1;
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
	x*=f;
}

#define rep(i,a,b) for(int i=a;i<b;++i)
typedef int ll;

const int MAXN=10005;

struct poi{
	ll x,y;
	inline void scan(){
		Scan(x),Scan(y);
	}
	poi(ll x=0,ll y=0):x(x),y(y){}
}p[MAXN];

inline poi operator-(const poi&a,const poi&b){
	return poi(a.x-b.x,a.y-b.y);
}
inline ll cross(const poi&a,const poi&b){
	return a.x*b.y-a.y*b.x;
}

int T,n,ans;

inline int calc(int s,int t){
	if(s==t)(++t)%=n;
	int res=0;
	rep(i,0,n)
		if(!cross(p[i]-p[s],p[t]-p[s]))++res;
	return res;
} 

inline void Solve(){
	Scan(n);
	rep(i,0,n)p[i].scan();
	ans=0;
	rep(i,0,1000){
		ans=max(ans,calc(rand()%n,rand()%n));
	}
	printf("%d\n",ans);
}

int main(){
	srand(time(0));
	for(Scan(T);T--;Solve()); 
	return 0;
}