Description
有一个由n台计算机组成的无线网络。(n <= 1001),正常情况下,每台计算机都能跟与它距离不超过d的任何计算机通讯(d <= 20000)。地震发生了。所有的计算机都陷入瘫痪。专家们试着一台一台地修复计算机,以恢复整个无线网络。有时在修复的过程中,他们需要测试一下某两台计算机能否通讯(如果他们能通过别的正常的计算机进行通讯,也算他们之间可以通讯,即“能否通讯”可以是间接的)。
你的任务,就是模拟修复网络的过程,并回答“能否通讯”的询问。
Input
第一行两个整数,N和d,N表示计算机的数目,d表示两台计算机直接可直接通讯的最大距离。接下来的N行,每行两个整数Xi,Yi,表示每台计算机的坐标。接下来有许多行,每行都是一个操作(或者是修复操作,或者是询问操作)。
操作的格式如下:
O p (1 <= p <= N) 修复操作,表示修复编号为p的电脑;
S p q (1 <= p, q <= N) 询问操作,询问编号为p和编号为q的电脑能否通讯。
如果一台电脑尚未被修复,则它不能和任何电脑通讯。
Output
对于每个询问操作:如果能够通讯,输出一行SUCCESS;如果无法通讯,输出一行FAIL
Sample Input
4 1
0 1
0 2
0 3
0 4
O 1
O 2
O 4
S 1 4
O 3
S 1 4
Sample Output
FAIL
SUCCESS
Data Constraint
Hint
【限制】
对于50%的数据,N <= 300, 操作次数 <= 10000;
对于100%的数据,N <= 1001, 操作次数 <= 300000。
分析
1.用勾股定理求出2点之间距离,然后判断每个点的d范围内存在的点。
2.做并差集,如果修复了第X台,就把与这台范围内的已经被修复了的点赋值第X台的标识。
3.询问时,先判断2台是否都被修复,如果是就进一步判断他们的标识是否相同,相同输出SUCCESS不然输出FAIL,如果任意一台未被修复直接输出FAIL。
程序:
var
s,x,y:array [0..1002] of longint;
w:array [0..1002,0..1002] of longint;
a:array [0..1002] of boolean;
g,h,i,j,n,m:longint;
b:char;
function find(a:longint):longint;
begin
if s[a]=a then exit(a);
s[a]:=find(s[a]);
exit(s[a]);
end;
procedure init;
begin
readln(n,m);
for i:=1 to n do
begin
readln(x[i],y[i]);
s[i]:=i;
end;
for i:=1 to n do
for j:=1 to n do
if sqrt(trunc(sqr(x[i]-x[j])+sqr(y[i]-y[j])))<=m then
begin
inc(w[i,0]);
w[i,w[i,0]]:=j;
end;
end;
procedure main;
begin
while not(eof) do
begin
read(b);
if b='O' then
begin
read(g);
a[g]:=true;
for j:=1 to w[g,0] do
if a[w[g,j]] then s[find(w[g,j])]:=find(g);
end else
begin
read(g,h);
if (a[g]=true)and(a[h]=true) then
begin
if find(g)=find(h) then writeln('SUCCESS') else writeln('FAIL');
end else writeln('FAIL');
end;
readln;
end;
end;
begin
init;
main;
end.