【Maratona de Programa¸c˜ao da SBC 2019 A】Artwork 并查集 模拟

The Mona Dura is one of the most valuable artworks in Nlogonia Museum. The famous painting is
displayed in a rectangular room of M by N meters. The room entrance is in a corner of it, while the
Mona is in the corner diagonally opposite to the entrance.
To prevent theft, the room has motion sensors that are activated every night when the museum
closes. Each sensor has a sensitivity S, such that the sensor triggers an alarm if it detects any movement
at no more than S meters from its location.
Tonight a thief broke into the museum with the purpose to steal the Mona Dura. To achieve his
goal, the thief needs to enter the room and reach the painting without being detected by any of the
motion sensors, that is, he must keep a distance longer to Si meters from the i-th motion sensor all
the time, for all the sensors.
The thief has access to the plants of the museum, therefore, he knows the size of the room, the
coordinates, and the sensitivities of each of the motion sensors. Given this information, your task is
to determine if it is possible for the thief to steal the Mona Dura.
Input
The first line of input contains three integer numbers, M, N, and K, representing the size of the
room, and the number of sensors, respectively. (10 ≤ M, N ≤ 104
, 1 ≤ K ≤ 1000). The entrance to
the room is located at position (0, 0), and the painting at position (M, N).
Each of the next K lines describes one of the K sensors, it contains three integer numbers, X,
Y , and S, where (X, Y ) represents the sensors location and S represents the sensor’s sensitivity.
(0 < X < M, 0 < Y < N, 0 < S ≤ 104
). All dimensions and coordinates in the input are in meters.
It is guaranteed that all sensors have different coordinates.
Output
Your program must output a single line containing the character ‘S’ in case the painting can be
stolen, or the character ‘N’ otherwise.
Input example 1
10 22 2
4 6 5
6 16 5
Output example 1
S
Input example 2
10 10 2
3 7 4
5 4 4
Output example 2
N
Input example 3
100 100 3
40 50 30
5 90 50
90 10 5
Output example 3
S

题意：一个矩形区域内有若干个圆，问能不能避开这些圆从左下角到右上角

思路：

破题口：如果出入口没有被圆罩住（封起来），而且没有任何相交的圆，那么肯定可以到达。为什么：极限着来想，我图里充满了各种各样的圆，但都没有相交，那我总可以从圆之间的缝隙中蛇皮走位穿过去（肯定是整数点坐标）来到达终点。
所以不能到达的情况只有以下几种：
1.出入口被封住
2.有一些连续的相交圆把竖直路径挡住了，如下图：

3.同上，但是水平方向被拦着了，如下图：

针对后两种，所以我们只需要对相交的圆看成一个集合，这个集合的上下左右边界都取这些圆的最值，看看超不超过上下或者左右边界即可。第一种情况除了直接罩住的之外，还有被围起来出不去或者进不去的情况也要讨论，方法一样。整个过程用并查集维护一下即可。

AC代码：

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 1e3+200;
const int inf=0x3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'|ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };

ll fa[maxn];
ll L[maxn];
ll R[maxn];
ll U[maxn];
ll D[maxn];

ll get(ll x)
{
    if(x==fa[x]) return x;
    return fa[x] = get(fa[x]);
}

void merge(ll x, ll y)
{
    ll a = get(x);
    ll b = get(y);
    if(a!=b)
    {
        L[b] = L[a] = min(L[a], L[b]);
        R[b] = R[a] = max(R[a],R[b]);
        U[b] = U[a] = max(U[a],U[b]);
        D[b] = D[a] = min(D[a],D[b]);
        fa[b] = a;
    }
}

typedef struct Pos
{
    double x;
    double y;
    double r;
    double up;
    double down;
    double L;
    double R;
}P;

P a[maxn];

int main()
{
    ll n = read(), m = read();
    ll k = read();
    int flag = 1;
    rep(i,1,k)
    {
        scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].r);
        double r = a[i].r;
        a[i].up = a[i].y+r;
        a[i].down = a[i].y - r;
        a[i].L = a[i].x - r;
        a[i].R = a[i].x + r;
        if(a[i].x*a[i].x + a[i].y*a[i].y <= a[i].r*a[i].r || (a[i].x - n)*(a[i].x-n) + (a[i].y-m)*(a[i].y-m) <= a[i].r*a[i].r) flag = 0;
        fa[i] = i, L[i] = a[i].L , R[i] = a[i].R, U[i] = a[i].up , D[i] = a[i].down;
    }
    if(!flag) cout<<"N"<<'\n';
    else
    {
        rep(i,1,k) rep(j,1,k)
             if( sqrt((a[i].x - a[j].x)*(a[i].x - a[j].x) + (a[i].y-a[j].y)*(a[i].y-a[j].y) ) <= a[i].r + a[j].r)
             {
                 merge(i,j);
             }
        rep(i,1,k) if(L[get(i)]<1&&R[get(i)]>n-1||D[get(i)]<1&&U[get(i)]>m-1||R[get(i)]>n-1&&U[get(i)]>m-1||L[get(i)]<1&&D[get(i)]<1) flag = 0;
        if(!flag) cout<<"N"<<'\n';
        else cout<<"S"<<'\n';
    }

    return 0;
}