J. The Volcano Eruption(并查集,思维)——东三

题目：http://codeforces.com/gym/101915/problem/J

题目大意：

在一个纵向为L，横向为w的区域上，有N个半径一般不同的圆形，圆形区域叠加在一起后就算连在一块。穿过一个圆形区域集需要消耗一件衣服。问：
你要从区域的下边穿过这个区域到达上端，需要最少衣服？

思路：

由图观察到，当左右两边都被圆形区域集触碰到了，那么对于这个圆形区域集的信息而言，有且有最少消耗1件衣服的方法通过这个圆形区域集。而左侧或右侧边没有被某个圆形区域集触碰到，那么对于这个区域集来说，总有一种办法可以通过这个区域集而不消耗衣服数量的。

思维

在还没学曲面几何的算法的时候，处理一个矩形区间的问题，采用垂直分问题法，即将矩形元素x，y平行处理。比如这道题，考虑到圆的对称性，应该着重观察圆点，半径以及区间边的关系。（照平行x，y轴的信息来分析）

可知对于C1而言，当p1(x1,y1) : x1+r>=w时，对于C1所在区域集的右侧就为被触碰到了，对于C2而言，当p2(x2,y2)：x2-r<=0时，对于C2所在区域集的左侧就为被触碰到了。
而当两侧被触碰到时，经过这个区域集，必消耗一件衣服。
然后通过两圆的圆点距离以及半径关系确定两圆是否相交。注意几何中元素平行x，y分解化，找出与矩形边关系的思想。
最后将各个圆用并查集处理，得到由m(m<=n)个区域集，由父节点负责代表区域集的信息。

以下附代码：

#include<cstdio>
#include<cmath>
#include<memory.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1005;
int fa[MAX_N];
ll n,w,l;
bool Left[MAX_N],Right[MAX_N];
struct point
{
    ll x,y;
    ll r;
}Point[MAX_N];

bool combine(point A,point B)
{
    long double r_r = A.r + B.r;
    long double dis = sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
    return dis-r_r<=0;
}


void init()
{
    for(int i=0;i<n;i++){
        fa[i] = i;
        Right[i] = 0;
        Left[i] = 0;
    }
}

int get(int x)
{
    if(fa[x]==x){
        return x;
    }
    int r = x;
    while(fa[r]!=r){
        r = fa[r];
    }
    return r;
}

void merg(int x,int y)
{
    int fx = get(x),fy = get(y);
    if(fx!=fy){
        fa[fx] = fy;
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        memset(Point,0,sizeof(Point));
        scanf("%lld%lld%lld",&n,&w,&l);
        init();
        for(int i=0;i<n;i++){
            scanf("%lld%lld%lld",&Point[i].x,&Point[i].y,&Point[i].r);
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(combine(Point[i],Point[j])) merg(i,j);
            }
        }
        for(int i=0;i<n;i++){
            if(Point[i].x-Point[i].r<=0) Left[get(i)]=1;
            if(Point[i].x+Point[i].r>=w) Right[get(i)]=1;
        }
        int ans=0;
        for(int i=0;i<n;i++){
            if(get(i)==i&&Left[get(i)]==1&&Right[get(i)]==1) ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}