自动搬运

查看原文

来自洛谷，原作者为

	Garen **

搬运于2025-08-24 22:02:46，当前版本为作者最后更新于2018-05-26 23:31:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

洛谷5月月赛的T2。让我大开眼界！

Drench大佬这么说的：

B. 偷上网

如果 $n = 1$，则枚举一下四个角，如果都不可行，一定无解，否则就找到了合法点。

如果 $n \geq 2$ ，则圆的总面积一定小于正方形的面积，每次随机一个点，判断是否可行。显然随机次数不会太多就会找到合法解。

所以有一种几乎不会被hack的算法，叫做随机算法！！！

如何取随机数？

只需要include进cstdlib，srand一个种子之后，就可以用rand()取随机数啦！

随机算法的优点是随机！我设计这种算法，即使运算100000次也根本不会超时，发现100000次还WA了一个点，直接再添一个0就可以了，并不会慢太多。时限很轻松。

srand的种子要取什么？

随缘！比如19260817、你自己的手机号、你基友的生日等等都可以。

这么多种子随便取，导致出题人都没办法hack你！

代码：

#include<cstdio>
#include<cmath>
#include<cstdlib>
using namespace std;
const int maxn = 15;
double x[maxn], y[maxn];
double n, l;
int main()
{
	srand(19260817);
	scanf("%lf%lf", &n, &l);
	for(int i = 1; i <= n; i++) scanf("%lf%lf", &x[i], &y[i]);
	for(int i = 1; i <= 1000000; i++)
	{
		double tx = rand(), ty = rand();
		while(tx > l) tx /= 10;
		while(ty > l) ty /= 10;
		bool ok = true;
		for(int j = 1; j <= n; j++)
		{
			if(pow(tx - x[j], 2) + pow(ty - y[j], 2) < pow(l / n, 2))
			{
				ok = false;
				break;
			}
		}
		if(ok)
		{
			printf("%.3lf %.3lf\n", tx, ty);
			return 0;
		}
	}
	printf("GG\n");
	return 0;
}