SGU198 题意就是一个圆形的船，然后有一些圆形的岛阻碍着船，问船能不能顺利出来。 做法就是把船的半径累加到岛中，这样只要判断 船的圆心，是否被一些圆包围。 可以使用SPFA去判断，有没有负环。
198. Get Out!
time limit per test: 0.25 sec. memory limit per test: 65536 KB
input: standard output: standard
Captain Faraway on his famous circular ship Kolobok is lost among the islands of the archipelago that he has just discovered. Now he wonders whether he can get out of there. Help him! All islands in the archipelago can be composed of pieces that have circular form. You are given the map of archipelago and the position of captain. Find out whether captain can get out of there, i.e. can get as far from the point he is in the beginning as he likes.
Input
The first line contains N — the number of circular island parts (1 ≤ N ≤ 300). N lines follow, each containing xi, yi, ri — coordinates of center and radius of the i-th circle. All coordinates and radii are real. Objects may overlap with each other in arbitrary way. All objects are considered solid. The last line of the input file contains three real numbers — coordinates of the center of Kolobok and its radius. You may consider Kolobok to be the perfect circle and that it is in the free area in the beginning. Kolobok can move along any trajectory and is so strong that he can even touch islands, but no nonzero part of island must intersect Kolobok during his motion. You may assume that making calculations with the precision of 10-6 is satisfactory.
Output
Output YES if Kolobok can leave archipelago and NO if it cannot.
Sample test(s)
Input
Test #1 7 2 2 1.1 -2 2 1.1 2 -2 1.0 -2 -2 1.0 2 -5 1.0 0 -8 1.0 -2 -6 1.0 0 0 1 Test #2 5 2 2 1.1 -2 2 1.1 2 -2 1.0 -2 -2 1.0 0 -3 0.01 0 0 1
Output
Test #1 YES Test #2 NO
/* ***
Author :kuangbin
Created Time :2014/11/10 20:16:21
File Name :D:\github\ACM-ICPC\SGU\SGU198.cpp
************************************************ */
#include <stdio.h>
#include <string.h>
#include
#include
#include
#include
#include
#include
#include
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const double eps = 1e-8;
const int MAXN = 310;
struct Circle{
double x,y,r;
Circle(double _x = 0,double _y = 0,double _r = 0){
x = _x; y = _y; r = _r;
}
void input(){
scanf(“%lf%lf%lf”,&x,&y,&r);
}
bool check(Circle b){
double d = hypot(x-b.x,y-b.y);
return d < r + b.r - eps;
}
Circle operator -(const Circle &b)const{
return Circle(x-b.x,y-b.y,0);
}
double operator (const Circle &b)const{
return x\b.x + y*b.y;
}
double operator ^(const Circle &b)const{
return x*b.y - y*b.x;
}
}circle[MAXN];
Circle p0;
double rad(Circle a,Circle b){
return atan2((a-p0)^(b-p0),(a-p0)*(b-p0));
}
struct Edge{
int to,next;
double w;
}edge[MAXN*MAXN];
int head[MAXN],tot;
void init(){
tot = 0;
memset(head,-1,sizeof(head));
}
inline void addedge(int u,int v,double w){
edge[tot].to = v;
edge[tot].w = w;
edge[tot].next = head[u];
head[u] = tot++;
}
double dist[MAXN];
bool vis[MAXN];
int cnt[MAXN];
bool SPFA(int n){
for(int i = 0;i < n;i++){
dist[i] = 0.0;
vis[i] = false;
cnt[i] = 0;
}
queue
for(int i = 0;i < n;i++){
vis[i] = true;
q.push(i);
cnt[i]++;
}
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = false;
for(int i = head[u];i != -1;i = edge[i].next){
int v = edge[i].to;
double w = edge[i].w;
if(dist[u] + w < dist[v] - eps){
dist[v] = dist[u] + w;
if(!vis[v]){
vis[v] = true;
cnt[v]++;
q.push(v);
if(cnt[v] > n)return false;
}
}
}
}
return true;
}
int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int n;
while(scanf(“%d”,&n) == 1){
for(int i = 0;i < n;i++)
circle[i].input();
p0.input();
for(int i = 0;i < n;i++)
circle[i].r += p0.r;
init();
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
if(i != j){
if(circle[i].check(circle[j]))
addedge(i,j,rad(circle[i],circle[j]));
}
if(SPFA(n))printf(“YES\n”);
else printf(“NO\n”);
}
return 0;
}
