P4703偷上网（题解）

发表于 | 更新于 | 阅读次数：
本文字数： 6.2k | 阅读时长 ≈ 6 分钟

这里有一篇题解。

P4703偷上网（题解）

点我

PS.

随机大法好用
我做这道题，刚开始忘了可能有无解情况，$\texttt{T}$了$\texttt{4}$个点，说明无解的就四个点
然后，又过了一段时间，终于把代码构对了后，发现随机种子也很重要。
刚开始，我用$\texttt{time(0)}$来当随机种子，$\texttt{Wa}$了一个点。
后来用其他的一些随机种子，结果都$\texttt{Wa}$了那一个点。
一气之下，我翻了一下题解，抄了楼上的$\texttt{19260817}$作为随机种字，莫名其妙就对了。
我感到特别玄学

Problem.

就是给你$\texttt{n}$个圆，然后让你找出一个点，使它没被任何圆覆盖。
输出这个点的坐标，没有则输出$\texttt{GG}$。

Solution.

没什么好分析的
直接暴力随机这个点的坐标，然后判断这个点是否在圆内。
那么如何判断这个点是否在圆内呢？ 不会的点我
具体详情请看代码。

Coding.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
const int N=15;
struct point{double x,y;}a[N];	//点的结构体
int n,l,m=1e7;	//m表示随机次数
inline point Rand()		//生成平面上的随机一个点
{
	double x=rand(),y=rand();
	while(x>l) x/=10;
	while(y>l) y/=10;
	return (point){x,y};
}
inline double sqr(double x) {return x*x;}	//平方函数
inline char check(point b)		//判断这个点是否在一个圆里面
{
	for(int i=1;i<=n;i++)
		if(sqr(b.x-a[i].x)+sqr(b.y-a[i].y)<sqr(double(l)/n))
			return 1;
	printf("%.3lf %.3lf\n",b.x,b.y);
	return 0;
}
int main()
{
	srand(19260817);	//玄学的随机种字
	scanf("%d%d",&n,&l);
	for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
	while(check(Rand())&&m--);	//不断随机点，判断
	if(m==-1) puts("GG");	//判断不可行解
	return 0;
}