SGU 198 Get Out! 6/10

好玩的題目

首先，把你的圓形船變成點，其他人膨脹(+sr)

接著如果兩個圓相交，就連一條線

如果你被包在一個封閉多邊形，你就出不去了

這邊有一個很有趣的性質：

線相交所產生的點圍出的環可以由這些島圍出更大的

（你就假設有個點，他可以把別人圍起來，弄一弄就發現可以用那些島的點圍起來）

有了這個特性，你只要判斷島點圍出的還即可(N個)

接下來，你先隨機弄一個射線（判斷是否在內）

看跟誰交在一起，接著你就用dfs走過這些點一遍

如果有back edge，你就判斷有沒有被關起來這樣

可以知道這樣就可以了，不需要去判斷所有的環

（因為要不是會重複，就是可以用已判斷過的環去組出來，所以完全不影響結果）

//By momo
#include
#include
#include
#include
#define N 310
#define EPS 1e-8
#define FOR(it, c) for(typeof((c).begin())it=(c).begin();it!=(c).end();it++)
using namespace std;

vector<int> G[N];
int n, dfn[N], ttl[N], tbl[N][N], fl = 1;

struct cord{
    double x, y, r;
}s, e, t[N];

double tx[N], ty[N], tr[N];
double sq(double d){ return d*d; }
double dis(int a, int b){
    return sqrt(sq(t[a].x-t[b].x)+sq(t[a].y-t[b].y));
}
double crs(cord a, cord b, cord c){
    double vx = a.x-c.x, vy = a.y-c.y;
    double ux = b.x-c.x, uy = b.y-c.y;
    return vx * uy - ux * vy;
}
bool hit(int a, int b){
    if(crs(t[b], s, t[a]) * crs(t[b], e, t[a]) < EPS
    && crs(   s, t[a], e) * crs(   s, t[b], e) < EPS) return 1;
    return 0;
}

void dfs(int p, int f, int l, int sum){
    dfn[p] = l; ttl[p] = sum;
    FOR(it, G[p]){
        if(*it == f) continue;
        if(dfn[*it] == -1) dfs(*it, p, l+1, sum+tbl[p][*it]);
        else if(dfn[*it] < dfn[p]){
            int cnt = sum - ttl[*it] + tbl[*it][p];
            if(cnt % 2) fl = 0;
        }
    }
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%lf%lf%lf", &t[i].x, &t[i].y, &t[i].r);
    scanf("%lf%lf%lf", &s.x, &s.y, &s.r);
    e.x = 214748364.3654427, e.y = -12923.1793283;
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            if(dis(i, j)+EPS < t[i].r + t[j].r + 2*s.r){
                G[i].push_back(j);
                G[j].push_back(i);
                tbl[i][j] = tbl[j][i] = hit(i, j);
            }
        }
    }
    fill(dfn, dfn+n, -1);
    for(int i = 0; i < n; i++)
        if(dfn[i] == -1) dfs(i, -1, 0, 0);
    puts(fl?"YES":"NO");
}