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
| #include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct Point
{
double x, y;
Point(double _x = 0, double _y = 0): x(_x), y(_y) {}
Point operator - (const Point &a)
{
return Point(x - a.x, y - a.y);
}
double operator * (const Point &a)
{
return x * a.x + y * a.y;
}
double operator ^ (const Point &a)
{
return x * a.y - y * a.x;
}
}a[1005];
int du[1005];
struct edge
{
int S, END, next, id;
}v[2005];
int first[1005], p;
void add(int c, int b, int id)
{
v[p].S = c;
v[p].END = b;
v[p].next = first[c];
v[p].id = id;
first[c] = p++;
}
double dis(const Point &x, const Point &y)
{
return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y));
}
struct line
{
Point a, b, c;
double k;
line() {}
line(Point x, Point y)
{
a = x, b = y;
c = a - b;
k = atan2(b.y - a.y, b.x - a.x);
}
}l[1005];
double dis(Point &x, line &y)
{
if ((y.c * (y.a - x)) * (y.c * (y.b - x)) <= 0)
return abs((y.a - x) ^ (y.b - x)) / dis(y.a, y.b);
return min(dis(y.a, x), dis(y.b, x));
}
bool f[1005][1005];
int n, stx, sty;
bool Judge(double mid)
{
memset (f, 0, sizeof (f));
queue<pair<int, int> > Q;
for (int i = first[stx]; i != -1; i = v[i].next)
f[sty][v[i].id] = 1, Q.push(pair<int, int>(sty, v[i].id));
for (int i = first[sty]; i != -1; i = v[i].next)
f[stx][v[i].id] = 1, Q.push(pair<int, int>(stx, v[i].id));
while (!Q.empty())
{
pair<int, int> k = Q.front(); Q.pop();
int x = k.first, y = k.second;
for (int i = first[x]; i != -1; i = v[i].next)
{
if (!f[v[i].END][y] && dis(a[v[i].END], l[y]) <= mid)
{
f[v[i].END][y] = 1;
Q.push(pair<int, int>(v[i].END, y));
}
if (!f[v[(y - 1) << 1].S][v[i].id] && dis(a[v[(y - 1) << 1].S], l[v[i].id]) <= mid)
{
f[v[(y - 1) << 1].S][v[i].id] = 1;
Q.push(pair<int, int>(v[(y - 1) << 1].S, v[i].id));
}
if (!f[v[(y - 1) << 1].END][v[i].id] && dis(a[v[(y - 1) << 1].END], l[v[i].id]) <= mid)
{
f[v[(y - 1) << 1].END][v[i].id] = 1;
Q.push(pair<int, int>(v[(y - 1) << 1].END, v[i].id));
}
}
}
for (int i = 1; i <= n; i++) if (du[i] == 1)
for (int j = 1; j <= n; j++) if (du[j] == 1)
if (f[i][v[first[j]].id] && dis(a[i], a[j]) <= mid)
return 1;
return 0;
}
int main()
{
memset (first, -1, sizeof (first));
n = read(), stx = read(), sty = read();
for (int i = 1; i <= n; i++)
a[i].x = read(), a[i].y = read();
for (int i = 1; i < n; i++)
{
int b = read(), c = read();
du[b]++, du[c]++;
add(b, c, i);
add(c, b, i);
l[i] = line(a[b], a[c]);
}
double l = dis(a[stx], a[sty]), r = 1e9;
while (abs(r - l) >= 1e-8)
{
double mid = (l + r) / 2;
if (Judge(mid)) r = mid;
else l = mid;
}
printf ("%.10f", l);
}
|
