JS's Blog
0%

UVA - 11853 - Paintball (dfs)

Posted on Edited on In ,

题目链接：
https://vjudge.net/contest/170743#problem/E

题目大意：
一个人要从x=0,x=1000,y=1000,y=0x=0,x=1000,y=1000,y=0在第一象限包围出的矩形的左侧走到右侧，途中会遇到很多圆，不能走入圆内，求出发点和到达点yy坐标最大的方案，若不可能输出IMPOSSIBLE

分析：
分析是否可行比较简单，从接触上边界的圆开始，dfs继续找所有与当前圆相交或者相切的圆，（内含理论上不必包含，但是这里包含并不影响正确性，而且代码逻辑更简单，所以没有特判），若发现接触下边界的圆，则说明不可能。

实际上这个过程用并查集也可以实现，设计一个up和down数组，表示该集合的最大坐标上界和下界，若两圆相交，则合并两圆的集合，最后fa[i]==ifa[i] == i 的即是根，遍历所有根查找是否上界超出1000且下界低于0，即可判定可行性。

比较麻烦的是找出yy坐标最大的解，实际上，画图可以发现，除了接触上界且接触左右界的圆集合，其他对答案都没有影响，可以通过"绕路"绕过，所以只要在dfs过程中，加上对当前圆与左右界是否相交的判断，然后算出最低交点的位置，与当前起点和终点分别取最小值即可。

代码：

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;

typedef long long ll;


double sqr(double x)
{
    return x*x;
}

struct Point{
    double x,y;
    Point(){}
    Point (double _x,double _y)
    {
        x = _x;
        y = _y;
    }
    void read()
    {
        scanf("%lf%lf",&x,&y);
    }
    double distance(Point a)
    {
        return hypot(x-a.x,y-a.y);
    }


};

struct Circle{
    Point p;
    double r;
    Circle(){}
    Circle(double _x,double _y,double _r)
    {
        p = Point(_x,_y);
        r = _r;
    }
    void read()
    {
        p.read();
        scanf("%lf",&r);
    }
    bool cross(Circle a)
    {
        double dis = p.distance(a.p);
        return dis<=r+a.r;
    }

}c[1200];

int n;
int vis[1200];
double a1,a2;

bool dfs(int k)
{
    //printf("now dfs(%d)\n",k);
    //cross left
    if (c[k].p.x<=c[k].r)
    {
        double t = sqrt(sqr(c[k].r)-sqr(c[k].p.x));
        a1 = min(a1,c[k].p.y-t);
    }
    //cross right
    if (1000-c[k].p.x<=c[k].r)
    {
        double t = sqrt(sqr(c[k].r)-sqr(1000-c[k].p.x));
        a2 = min(a2,c[k].p.y-t);
    }
    //cross bottom
    if (c[k].p.y<=c[k].r)
        return false;
    bool res = true;
    for (int i = 1 ; i <= n ; i ++)
    {
        if (!vis[i]&&c[k].cross(c[i]))
        {
            vis[i] = 1;
            if (!dfs(i))
            {
                res = false;
                break;
            }
            
        }
    }
    return res;
}



int main()
{
    while (~scanf("%d",&n))
    {
        memset(vis,0,sizeof(vis));
        a1 = a2 = 1000.0;

        for (int i = 1 ; i <= n ; i ++)
        {
            c[i].read();
        }
        int f = 1;
        for (int i = 1 ; i <= n ; i ++)
        {
            if (!vis[i]&&c[i].p.y+c[i].r>=1000.0)
            {
                vis[i] = 1;
                if (!dfs(i))
                {

                    printf("IMPOSSIBLE\n");
                    f = 0;
                    break;
                }
            }
        }
        if (f)
            printf("%.2f %.2f %.2f %.2f\n",0.0,a1,1000.0,a2);

    }
    return 0;
}