-
Notifications
You must be signed in to change notification settings - Fork 2
/
战场.cpp
59 lines (52 loc) · 1.13 KB
/
战场.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
const int maxn = 1000+10;
const double w = 1000.0;
int vis[maxn];
double x[maxn], y[maxn], r[maxn];
int n; //敌人个数
double left,right;
bool intersect(int a, int b){ // 判断两圆是否相交
return sqrt( (x[a]-x[b])*(x[a]-x[b]) + (y[a] - y[b])*(y[a]-y[b]) ) < r[a]+r[b];
}
void check(int i){
if(x[i]-r[i]<0){
left = std::min(left, y[i] - sqrt(r[i]*r[i] - x[i]*x[i]));
}
if(x[i] + r[i] >w){
right = std::min(right, y[i] - sqrt( r[i]*r[i] - (w - x[i])*(w-x[i]) ));
}
}
bool dfs(int i){
// if(vis[i]) return false;
vis[i] = 1;
if(y[i] - r[i]<0) return true;
for(int k = 0; k<n;k++){
if(!vis[k] && intersect(i, k) && dfs(k) ){
return true;
}
}
check(i);
return false;
}
int main(){
while(scanf("%d", &n)!=EOF){
memset(vis, 0, sizeof(vis));
left = right = w;
bool f = true;
for(int i = 0; i<n;i++){
scanf("%lf%lf%lf", &x[i], &y[i], &r[i]);
}
for(int i = 0; i<n;i++){
if(y[i]+r[i] >= w &&!vis[i] && dfs(i)){
f = 0;
break;
}
}
if(f) printf("0.00 %.2lf %.2lf %.2lf\n", left, w, right);
else printf("IMPOSSIBLE\n");
}
return 0;
}