[ACdream 1215 Get Out!]判断点在封闭图形内, 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=;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?:-;
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?:-;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 + ;int dcmp(double x) {
if (fabs(x) < EPS) return ;
return x > ? : - ;
}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) > ) {
v = u + w;
return true;
}
return false;
}bool spfa(int s) {
queue<int> Q;
Q.push(s);
fillchar(vis, );
for (int i = ; i < n; i ++) {
d[i] = INF;
}
fillchar(cnt, );
d[s] = ;
while (!Q.empty()) {
int H = Q.front(); Q.pop();
vis[H] = false;
for (int i = ; 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 = ; 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, , ) / dist(b.x, b.y, , ));
if (dcmp(a.x * b.y - a.y * b.x) <= ) return angle;
return - angle;
}int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
while (cin >> n) {
for (int i = ; i < n; i ++) {
p[i].read();
}
Circle me;
me.read();
for (int i = ; i < n; i ++) {
p[i].x -= me.x;
p[i].y -= me.y;
}
for (int i = ; i < n; i ++) {
for (int j = ; j < n; j ++) {
e[i][j] = INF + ;
}
}
for (int i = ; i < n; i ++) {
for (int j = i + ; 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 * ) < ) {
e[i][j] = calcangle(i, j);
e[j][i] = - e[i][j];
//Debug::print(i, j, e[i][j]);
}
}
}
work();
}
return ;
}