NOIP2014 奶酪
题面：
NOIP2014 提高组 D2T1
现有一块大奶酪，它的高度为 \(h\)，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系，在坐标系中，奶酪的下表面为 \(z = 0\)，奶酪的上表面为 \(z = h\)。
现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，特别地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；如果一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。
位于奶酪下表面的 Jerry 想知道，在不破坏奶酪的情况下，能否利用已有的空洞跑 到奶酪的上表面去?
空间内两点 \(P_1(x_1,y_1,z_1)\)、\(P2(x_2,y_2,z_2)\) 的距离公式如下：
对于 \(20\%\) 的数据，\(n = 1\)，\(1 \le h\)，\(r \le 10^4\)，坐标的绝对值不超过 \(10^4\)。
对于 \(40\%\) 的数据，\(1 \le n \le 8\)，\(1 \le h\)，\(r \le 10^4\)，坐标的绝对值不超过 \(10^4\)。
对于 \(80\%\) 的数据，\(1 \le n \le 10^3\)，\(1 \le h , r \le 10^4\)，坐标的绝对值不超过 \(10^4\)。
对于 \(100\%\) 的数据，\(1 \le n \le 1\times 10^3\)，\(1 \le h , r \le 10^9\)，\(T \le 20\)，坐标的绝对值不超过 \(10^9\)。
（题面复制于洛谷）
思考：
这道题非常地蒟蒻，蒟蒻到 \(\texttt{Tw}\) 拿他来水题解 ……
直接看 \(100\%\) 的数据吧， \(1 \le n \le 1\times 10^3\) ，显然是时间复杂度为 \(\operatorname{O}(n^2)\) 的。
辣么算法就很明显啦~
每次枚举一对（两个）奶酪洞，判断他们是否相连
如何判断？只要判断他们的距离是否小于等于他们的半径之和就可以了
（什么相切相交的，都是幌子，
都是一本正经的废话，其实说白了就是上面的）如果相连，那么就把两个洞加到同一个并查集里（其实这里有点问题，因为并查集操作是 \(\operatorname{O}(lgn)\) 的，但还是卡过去了）
如果这个洞能通到上面，加入一个 \(\texttt{vector}\) ；若能通到下面，加入另一个。
最后暴力枚举两个 \(\texttt{vector}\) ，判断是否在同一并查集。
于是乎，我
水了一篇题解A C 了一道题
代码：
#include<bits/stdc++.h>
using namespace std;
int t,n;
double x[1005],y[1005],z[1005],h,r;
int fa[1005],d[1005],p[1005];
int findfa(int x) {
return fa[x]==x?x:(fa[x]=findfa(fa[x]));
}
void join(int x,int y) {
int fax=findfa(x),fay=findfa(y);
fa[fay]=fax;
return ;
}
double P(double x) {
return x*x;
}
int main() {
scanf("%d",&t);
while(t--) {
scanf("%d%lf%lf",&n,&h,&r);
int l1=0,l2=0;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=n;i++) {
scanf("%lf%lf%lf",&x[i],&y[i],&z[i]);
for(int j=1;j<i;j++) {
double t=sqrt(P(x[i]-x[j])+P(y[i]-y[j])+P(z[i]-z[j]));
if(t<=2*r) join(i,j);
}
if(z[i]+r>=h) d[++l1]=i;
if(z[i]-r<=0.00) p[++l2]=i;
}
bool k=false;
for(int i=1;i<=l1;i++)
for(int j=1;j<=l2;j++)
if(findfa(d[i])==findfa(p[j])) {
k=true;
break;
}
if(k) printf("Yes\n");
else printf("No\n");
}
return 0;
}