大致题意：在二维平面上，给一些圆形岛屿的坐标和半径，以及圆形船的位置和半径，问能否划到无穷远的地方去
思路：考虑任意两点，如果a和b之间船不能通过，则连一条边，则问题转化为判断点是否在多边形中。先进行坐标变换，将船变到原点，以从起点到每个点的有向角作为状态，每条边的边权为这条边对有向角的改变量，那么点在多边形内相当于存在负权环，从每个点出发跑一下SPFA判负环即可。
#pragma comment(linker, "/STACK:10240000") #include <map> #include <set> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <vector> #include <cstdio> #include <string> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm>using namespace std;#define X first #define Y second #define pb push_back #define mp make_pair #define all(a) (a).begin(), (a).end() #define fillchar(a, x) memset(a, x, sizeof(a)) #define fillarray(a, b) memcpy(a, b, sizeof(a))typedef long long ll; typedef pair<int, int> pii; typedef unsigned long long ull;#ifndef ONLINE_JUDGE namespace Debug { void RI(vector<int>&a,int n){a.resize(n);for(int i=0;i<n;i++)scanf("%d",&a[i]);} void RI(){}void RI(int&X){scanf("%d",&X);}template<typename...R> void RI(int&f,R&...r){RI(f);RI(r...);}void RI(int*p,int*q){int d=p<q?1:-1; while(p!=q){scanf("%d",p);p+=d;}}void print(){cout<<endl;}template<typename T> void print(const T t){cout<<t<<endl;}template<typename F,typename...R> void print(const F f,const R...r){cout<<f<<", ";print(r...);}template<typename T> void print(T*p, T*q){int d=p<q?1:-1;while(p!=q){cout<<*p<<", ";p+=d;}cout<<endl;} } #endif // ONLINE_JUDGEtemplate<typename T>bool umax(T&a, const T&b){return b<=a?false:(a=b,true);} template<typename T>bool umin(T&a, const T&b){return b>=a?false:(a=b,true);}const double PI = acos(-1.0); const int INF = 0x3f3f3f3f; const double EPS = 1e-8;/* -------------------------------------------------------------------------------- */const int maxn = 3e2 + 7;int dcmp(double x) {if (fabs(x) < EPS) return 0;return x > 0? 1 : - 1; }struct Circle {double x, y, r;Circle(double x, double y, double r) {this->x = x;this->y = y;this->r = r;}void read() {scanf("%lf%lf%lf", &x, &y, &r);}Circle() {} }; Circle p[maxn];double e[maxn][maxn], d[maxn]; bool vis[maxn]; int n, cnt[maxn];double dist(double x1, double y1, double x2, double y2) {return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); }bool relax(double u, double w, double &v) {if (dcmp(v - u - w) > 0) {v = u + w;return true;}return false; }bool spfa(int s) {queue<int> Q;Q.push(s);fillchar(vis, 0);for (int i = 0; i < n; i ++) {d[i] = INF;}fillchar(cnt, 0);d[s] = 0;while (!Q.empty()) {int H = Q.front(); Q.pop();vis[H] = false;for (int i = 0; i < n; i ++) {if (e[H][i] < INF) {if (relax(d[H], e[H][i], d[i]) && !vis[i]) {if (cnt[i] >= n) return true;Q.push(i);vis[i] = true;cnt[i] ++;}}}}return false; }void work() {for (int i = 0; i < n; i ++) {if (spfa(i)) {puts("NO");return ;}}puts("YES"); }double calcangle(int i, int j) {Circle a = p[i], b = p[j];double angle = acos((a.x * b.x + a.y * b.y) / dist(a.x, a.y, 0, 0) / dist(b.x, b.y, 0, 0));if (dcmp(a.x * b.y - a.y * b.x) <= 0) return angle;return - angle; }int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout); #endif // ONLINE_JUDGEwhile (cin >> n) {for (int i = 0; i < n; i ++) {p[i].read();}Circle me;me.read();for (int i = 0; i < n; i ++) {p[i].x -= me.x;p[i].y -= me.y;}for (int i = 0; i < n; i ++) {for (int j = 0; j < n; j ++) {e[i][j] = INF + 1;}}for (int i = 0; i < n; i ++) {for (int j = i + 1; j < n; j ++) {double buf = dist(p[i].x, p[i].y, p[j].x, p[j].y) - p[i].r - p[j].r;if (dcmp(buf - me.r * 2) < 0) {e[i][j] = calcangle(i, j);e[j][i] = - e[i][j];//Debug::print(i, j, e[i][j]);}}}work();}return 0; }
