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;

}

巴特西

zoj2318

zoj2318

题意

分析

code

最新文章

热门文章