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<bits/stdc++.h>
using namespace std;
#define pb push_back
const int maxn = 8e2 + 9;
#define eps 1e-8
int sgn(double x) {
if(fabs(x) < eps) return 0;
else return x < 0 ? -1 : 1;
}
struct Point {
double x, y;
Point() {}
Point(double x, double y):x(x),y(y) {}
Point operator - (Point B) {
return Point(x - B.x, y - B.y);
}
bool operator == (Point B){return sgn(x - B.x) == 0 && sgn(y - B.y) == 0;}
} P[maxn], st, ed;
struct Line {
Point p1, p2;
Line() {}
Line(Point p1, Point p2):p1(p1),p2(p2) {}
} L[maxn];
int n;
struct Edge {
int v;
double w;
Edge(int _v = 0, double _w = 0) {
v = _v;
w = _w;
}
};
vector<Edge>G[maxn];
double Dist(Point A, Point B) {
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
double Cross(Point A, Point B) {
return A.x * B.y - A.y * B.x;
}
bool intersect(Point a, Point b, Point c, Point d){
if(a == c || a == d) return 0;
if(b == c || b == d) return 0;
return
max(a.x, b.x) >= min(c.x, d.x)&&
max(c.x, d.x) >= min(a.x, b.x)&&
max(a.y, b.y) >= min(c.y, d.y)&&
max(c.y, d.y) >= min(a.y, b.y)&&
sgn(Cross(b - a, c - a)) * sgn(Cross(b - a, d - a)) <= 0&&
sgn(Cross(d - c, a - c)) * sgn(Cross(d - c, b - c)) <= 0;
}
const double inf = 0x3f3f3f3f;
int vis[maxn], num;
double dis[maxn];
struct node {
int id; double s;
bool operator<(const node &A)const{
return A.s < s;}
};
bool check(Point a, Point b) {
for(int i = 1; i <= num; i++) {
if(i % 4 == 1) {
if(intersect(a, b, P[i], P[i + 2]) || intersect(a, b, P[i + 1], P[i + 3])) return 0;
}
if(i % 4 == 0 && intersect(a, b, P[i], P[i - 3])) return 0;
if(i % 4 != 0 && intersect(a, b, P[i], P[i + 1])) return 0;
}
return 1;
}
void Dij () {
for (int i = 1; i <= num; ++i) dis[i] = 99999999.0;
priority_queue<node> Q;
dis[0] = 0;
Q.push({0, 0.0});
while (Q.size()) {
node u = Q.top(); Q.pop();
if (u.id == num) return (void)(printf("%.20f\n", u.s));
if (vis[u.id]) continue;
vis[u.id] = 1;
for (int i = 0, sz = G[u.id].size(); i < sz; ++i) {
int v = G[u.id][i].v;
double d = G[u.id][i].w;
if (vis[v]) continue;
if (dis[v] - (dis[u.id] + d) > eps) {
dis[v] = dis[u.id] + d;
Q.push({v, dis[v]});
}
}
}
}
void solve() {
scanf("%d", &n);
if(n == 0) {
scanf("%lf %lf %lf %lf", &st.x, &st.y, &ed.x, &ed.y);
printf("%.20f\n", Dist(st, ed));
return ;
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= 4; j++) {
num++;
scanf("%lf %lf", &P[num].x, &P[num].y);
}
}
num++;
scanf("%lf %lf %lf %lf", &P[0].x, &P[0].y, &P[num].x, &P[num].y);
for(int i = 0; i < num; i++) {
for(int j = i + 1; j <= num; j++) {
if(check(P[i], P[j])) {
G[i].pb({j, Dist(P[i], P[j])});
G[j].pb({i, Dist(P[i], P[j])});
}
}
}
Dij();
}
int main() {
int t = 1;
while(t--)
solve();
return 0;
}
|
