补题 [ABC304C] Virus

题目描述

二维平面上有编号为 $1, 2, \ldots, N$ 的 $N$ 个人，第 $i$ 个人位于坐标为 $(X_i,Y_i)$ 的点。

第 $1$ 个人感染了病毒。病毒会从感染者传播给距离感染者 $D$ 以内的人。

这里，距离定义为欧几里得距离，即对于两个点 $(a_1,a_2)$ 和 $(b_1,b_2)$，这两个点之间的距离为 $\sqrt{(a_1-b_1)^2 + (a_2-b_2)^2}$。

经过足够长的时间后，即当第 $i$ 个人感染病毒时，与第 $i$ 个人距离在 $D$ 以内的所有人都感染了病毒，请确定每个 $i$ 是否感染了病毒。

输入格式

输入按以下格式从标准输入中给出：

$N$ $D$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_N$ $Y_N$

输出格式

输出 $N$ 行。第 $i$ 行，如果第 $i$ 个人感染了病毒，则输出 Yes；否则输出 No。

样例 #1

输入样例 #1

1
2
3
4
5
4 5
2 -1
3 1
8 8
0 5

输出样例 #1

1
2
3
4
Yes
Yes
No
Yes

样例 #2

输入样例 #2

1
2
3
4
3 1
0 0
-1000 -1000
1000 1000

输出样例 #2

1
2
3
Yes
No
No

样例 #3

输入样例 #3

1
2
3
4
5
6
7
8
9
10
9 4
3 2
6 -1
1 6
6 5
-2 -3
5 3
2 -3
2 1
2 6

输出样例 #3

1
2
3
4
5
6
7
8
9
Yes
No
No
Yes
Yes
Yes
Yes
Yes
No

提示

约束条件

  • $1 \leq N, D \leq 2000$
  • $-1000 \leq X_i, Y_i \leq 1000$
  • 当 $i \neq j$ 时，$(X_i,Y_i) \neq (X_j,Y_j)$。
  • 所有输入值都是整数。

样例解释 #1

第 $1$ 个人和第 $2$ 个人之间的距离为 $\sqrt{5}$，因此第 $2$ 个人感染了病毒。此外，第 $2$ 个人和第 $4$ 个人之间的距离为 $5$，因此第 $4$ 个人也感染了病毒。由于第 $3$ 个人周围没有距离在 $5$ 以内的人，所以他不会感染病毒。

题解

题目解析

我一开始貌似是用的sort优化最后遍历,但是不知道为什么大部分测试点没有AC.去B站看了看视频,他们用了个新方法:

  • 把距离小于D的所有点连接起来,形成一个联通图.最后从感染点出发,BFS遍历所有点.

因为第一次写图论代码,我之前从雨巨那里学到了链式前向星,别人用的邻接数组.我干脆用链式前向星试试水,于是有了这个代码.

AC代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;

#define int long long
#define endl "\n"
#define MAXN(size) const long long MAXN = size + 100//明明都开了2100了都炸数组了= =
#define var(size) int p[size]{}
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(a,n,p) for(int i=a;i<=n;i+=p)
#define fb(a,n,p) for(int i=a;i>=n;i-=p)
#define cin(length,var) for(int i=1;i<=length;i++) cin >> var[i]
typedef long long ll;

MAXN(2100);//一开始开的2000,RE了= =...现在其实是2200
int m=0,head[MAXN],vis[MAXN];
struct ty{
	int t,next;
}edge[MAXN*MAXN];

void insertedge(int a,int b){
	edge[++m].t = b;
	edge[m].next = head[a];
	head[a] = m;
}

struct Point{
	int x,y;
	double operator - (const Point &p)const{//重载运算符
		return sqrt((p.x-x)*(p.x-x)+(p.y-y)*(p.y-y));
	}
}p[MAXN];

signed main(){
	int n,d;
	mem(head,-1);
	cin >> n >> d;
	fa(1,n,1){
		cin >> p[i].x >> p[i].y;
	}
	fa(1,n,1){
		for(int j=1;j<=n;j++){
			if(p[i]-p[j] <= d){
				insertedge(i,j),insertedge(j,i);
			}
		}
	}
	queue<int> q;
	vis[1] = 1;
	q.push(1);
	while(!q.empty()){
		int temp = q.front();q.pop();
		for(int i=head[temp];i!=-1;i=edge[i].next){
			if(vis[edge[i].t]) continue;
			vis[edge[i].t] = 1;
			q.push(edge[i].t);
		}
	}
	fa(1,n,1){
		cout << (vis[i]?"Yes":"No") << endl;
	}
	return 0;
}