zoj2318

zoj2318

题意

一个平面上给出很多圆，其中一个圆为现在自己的位置，问这个圆能不能冲出其它圆的包围（不能与其它圆相交）。

分析

将所有圆心平移，使得自己的圆圆心处于原点，将所有圆半径增加自己圆的半径，这样自己的圆可以看成一个点，任意两圆相交我们都可以看作圆心间连了一条边，问题就转化成了一个点是否在一个多边形内，对于两点 (A) (B) ，我们可以把 (A-B) 这条有向边的权值置为角(AOB) 的角度，(B-A) 这条边的权值为角度取负，如果一个点在多边形内，那么跑一圈必然是 (2*PI) 或 (-2*PI) ，否则是 (0) ，跑一遍 (Bellman-Ford) 判断有无负环即可。

code

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e2 + 10;
const int MOD = 998244353;
const double EPS = 1e-9;
typedef long long ll;
int Sgn(double x) {
    if(fabs(x) < EPS) return 0;
    return x < 0 ? -1 : 1;
}
double Sqr(double x) {
    return x * x;
}
struct Circle {
    double x, y, r;
    double dist(Circle c) {
        return hypot(x - c.x, y - c.y);
    }
    bool Intersect(Circle c) {
        return Sgn(c.r + r - dist(c)) > 0;
    }
};
double Cross(Circle c1, Circle c2) {
    return c1.x * c2.y - c2.x * c1.y;
}
double Dot(Circle c1, Circle c2) {
    return c1.x * c2.x + c1.y * c2.y;
}
double Length(Circle c) {
    return hypot(c.x, c.y);
}
double Angle(Circle c1, Circle c2) {
    return acos(Dot(c1, c2) / Length(c1) / Length(c2));
}
Circle a[MAXN];
struct Edge {
    int from, to;
    double w;
    Edge(int from = 0, int to = 0, double w = 0) : from(from), to(to), w(w) {}
}es[MAXN * MAXN];
double d[MAXN];
int n, cnt;
bool find_negative_loop() {
    memset(d, 0, sizeof d);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < cnt; j++) {
            Edge e = es[j];
            if(Sgn(d[e.to] - d[e.from] - e.w) > 0) {
                d[e.to] = d[e.from] + e.w;
                if(i == n - 1) return true;
            }
        }
    }
    return false;
}
int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        cnt = 0;
        scanf("%d", &n);
        for(int i = 0; i < n; i++) {
            scanf("%lf%lf%lf", &a[i].x, &a[i].y, &a[i].r);
        }
        Circle O;
        scanf("%lf%lf%lf", &O.x, &O.y, &O.r);
        for(int i = 0; i < n; i++) {
            a[i].x -= O.x;
            a[i].y -= O.y;
            a[i].r += O.r;
        }
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                if(a[i].Intersect(a[j])) {
                    Circle c1 = a[i], c2 = a[j];
                    double sgn = 1;
                    if(Cross(c1, c2) < 0) sgn = -1;
                    double ang = Angle(c1, c2);
                    es[cnt++] = Edge(i, j, sgn * ang);
                    es[cnt++] = Edge(j, i, sgn * -ang);
                }
            }
        }
        puts(!find_negative_loop() ? "YES" : "NO");
        if(T) puts("");
    }
    return 0;
}