CodeChef MSTONES Milestones

传送门

题意：
平面上有n个点，已知不超过7条直线覆盖所有点。求在平面上的一条直线最多覆盖多少个点。

题解：
证明自己做过随机化的题
很显然可以发现一个会T的做法：枚举两个点，然后再枚举所有点求出直线覆盖点的个数。这玩意$O(n^3)$O(n3)的 CF评测机都肯定过不去。

（然后后面就是看了某论文才get到的做法）

显然我们可以发现覆盖最多点的直线覆盖了至少$\left \lceil \frac{n}{7} \right \rceil$⌈7n​⌉个点。
然后随机两个点，确定的直线满足题意的概率为$\frac{1}{49}$491​。
然后随机个几百上千次正确率就很大了。
然后判断点在直线上应该都会吧不讲了。

代码：

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define maxn 10005
using namespace std;
int n,t,x[maxn],y[maxn];
int main()
{
	srand(77);
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
		int ans=1;
		for(int k=1;k<=500;k++)
		{
			int u=rand()%n+1,v=rand()%n+1,tmp=0;
			if(u==v) continue;
			for(int i=1;i<=n;i++) tmp+=((x[u]-x[v])*(y[v]-y[i])==(x[v]-x[i])*(y[u]-y[v]));
			ans=max(ans,tmp);
		}
		printf("%d\n",ans);
	}
}

吐槽：
我锌钛稳着呢，才没崩。