题目大意:
一个由n台计算机组成的无线网络,每台计算机都能跟与它距离不超过d的任何计算机通讯。地震时,所有计算机都瘫痪了。在修复的过程中,他们需要测试一下某两台计算机能否通讯(如果他们能通过别的正常的计算机进行通讯,也算他们之间可以通讯,即“能否通讯”可以是间接的)。给出操作S,
S=“O”,则给出X,表示修复了第X台。
S=“S”,则给出X,Y,表示讯问第X,Y台是否连通。
给出每个计算机的坐标为a[i],b[i],以及多个操作,你的任务,就是模拟修复网络的过程,并回答“能否通讯”的询问,能输出SUCCESS否则输出FAIL。
对于50%的数据,N <= 300, 操作次数 <= 10000;
对于100%的数据,N <= 1001, 操作次数 <= 300000
d <= 20000
1 <= p, q <= N
如果一台电脑尚未被修复,则它不能和任何电脑通讯。
题解:
1.用勾股定理求出2点之间距离,然后判断每个点的d范围内存在的点。
2.做并差集,如果修复了第X台,就把与这台范围内的已经被修复了的点赋值第X台的标识。
3.询问时,先判断2台是否都被修复,如果是就进一步判断他们的标识是否相同,相同输出SUCCESS不然输出FAIL,如果任意一台未被修复直接输出FAIL。
varf,x,y:array [0..1002] of longint;xy:array [0..1002,0..1002] of longint;a:array [0..1002] of boolean;p,q,i,j,n,m:longint;s:string;pq:char;function find(a:longint):longint;
beginif f[a]=a then exit(a);f[a]:=find(f[a]);exit(f[a]);
end;beginreadln(n,m);for i:=1 to n dobeginreadln(x[i],y[i]);f[i]:=i;end;for i:=1 to n dofor j:=1 to n doif sqrt(trunc(sqr(x[i]-x[j])+sqr(y[i]-y[j])))<=mthen begininc(xy[i,0]);xy[i,xy[i,0]]:=j;end;while not(eof) dobeginread(pq);if pq='O'then beginread(p);a[p]:=true;for j:=1 to xy[p,0] doif a[xy[p,j]] then f[find(xy[p,j])]:=find(p);endelse beginread(p,q);if (a[p]) and (a[q])then begin if find(p)=find(q) then writeln('SUCCESS')else writeln('FAIL');endelse writeln('FAIL');end;readln;end;
end.