/**
_ _ __ _ _ _ _ _ _
|a ||t ||o d | |o |
| __ _| | _ | __| _ |
| __ |/_ | __ /__\ / _\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N_MAX = 100;
const int V_MAX = N_MAX * 4 + 4;
const ld INF = LLONG_MAX;
const int R = 100;
int N, S;
struct Point {
ld x, y;
};
ld dist (Point A, Point B) {
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
struct Segment {
Point A, B;
ld len () {
return dist(A, B);
}
};
Segment fence[N_MAX + 2];
Point project (Point P, Segment s) {
if (s.A.x == s.B.x) {
return Point{s.A.x, P.y};
} else if (s.A.y == s.B.y) {
return Point{P.x, s.A.y};
} else {
ld mAB = (ld) (s.A.y - s.B.y) / (s.A.x - s.B.x);
ld mPQ = -1 / mAB;
Point Q;
Q.x = (P.y - s.A.y - P.x * mPQ + s.A.x * mAB) / (mAB - mPQ);
Q.y = P.y + (Q.x - P.x) * mPQ;
return Q;
}
}
bool is_inside (Point P, Segment s) {
return (min(s.A.x, s.B.x) <= P.x && P.x <= max(s.A.x, s.B.x)
&& min(s.A.y, s.B.y) <= P.y && P.y <= max(s.A.y, s.B.y));
}
bool check (Segment s) {
Point mid = Point{(s.A.x + s.B.x) / 2, (s.A.y + s.B.y) / 2};
if (-S < mid.x && mid.x < S && -S < mid.y && mid.y < S) {
return false;
}
for (int side = 0; side < 4; side++) {
if (s.A.y > s.B.y) {
swap(s.A, s.B);
}
if (s.A.y < S && S < s.B.y) {
ld x;
if (s.A.x != s.B.x) {
x = s.A.x + (ld) (s.B.x - s.A.x) * (S - s.A.y) / (s.B.y - s.A.y);
} else {
x = s.A.x;
}
if (-S < x && x < S) {
return false;
}
}
swap(s.A.x, s.A.y); s.A.x *= -1;
swap(s.B.x, s.B.y); s.B.x *= -1;
}
return true;
}
Point corner[4];
int V;
Point get_point (int u) {
if (u <= N * 2) {
if (u % 2 == 1) {
return fence[u / 2 + 1].A;
} else {
return fence[u / 2].B;
}
} else {
return corner[u - N * 2 - 1];
}
}
struct Edge {
int to;
ld len;
bool trigo;
};
bool is_trigo (Segment s) {
return (s.A.x * s.B.y - s.A.y * s.B.x > 0);
}
vector <Edge> out[V_MAX + 2];
void add_edge (int u, int v, Segment s, bool is_fence = false) {
Point A = s.A, P = s.B, B = get_point(v);
ld len = (is_fence == false ? s.len() : 0);
bool trigo = is_trigo(Segment{A, B});
if (P.x != B.x || P.y != B.y) {
if (is_trigo(Segment{A, P}) != trigo && is_trigo(Segment{P, B}) != trigo) {
trigo = !trigo;
}
}
out[u].push_back(Edge{v, len, trigo});
swap(s.A, s.B); trigo = !trigo;
out[v].push_back(Edge{u, len, trigo});
}
int get_quad (Point P) {
if (P.x >= 0 && P.y > 0) {
return 0;
} else if (P.x < 0 && P.y >= 0) {
return 1;
} else if (P.x <= 0 && P.y < 0) {
return 2;
} else {
return 3;
}
}
ld min_dist[V_MAX + 2][R * 2 + 2];
bool seen[V_MAX + 2][R * 2 + 2];
struct Path {
int u;
int var;
ld len;
};
bool operator < (const Path &p1, const Path &p2) {
return p1.len > p2.len;
}
ld answer = LLONG_MAX;
void Dijkstra (int start) {
priority_queue <Path> q;
for (int u = 1; u <= V; u++) {
for (int var = -R; var <= R; var++) {
min_dist[u][var + R] = INF;
seen[u][var + R] = false;
}
}
min_dist[start][0 + R] = 0;
q.push(Path{start, 0, 0});
while (q.empty() == false) {
Path p = q.top(); q.pop();
if (seen[p.u][p.var] == true) {
continue;
}
seen[p.u][p.var] = true;
if (p.len > answer) {
continue;
}
if (p.u == start && p.var == 4) {
answer = p.len;
}
Point A = get_point(p.u);
for (Edge e : out[p.u]) {
Point B = get_point(e.to);
Path pe; pe.u = e.to; pe.len = p.len + e.len;
int delta = get_quad(B) - get_quad(A);
if (e.trigo == true) {
if (delta < 0) {
delta += 4;
}
} else {
if (delta > 0) {
delta -= 4;
}
}
pe.var = p.var + delta;
if (-R <= pe.var && pe.var <= R) {
if (pe.len < min_dist[pe.u][pe.var + R]) {
min_dist[pe.u][pe.var + R] = pe.len;
q.push(pe);
}
}
}
}
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(10);
cin >> N >> S;
for (int i = 1; i <= N; i++) {
cin >> fence[i].A.x >> fence[i].A.y;
cin >> fence[i].B.x >> fence[i].B.y;
}
corner[0] = Point{S, S};
corner[1] = Point{-S, S};
corner[2] = Point{-S, -S};
corner[3] = Point{S, -S};
for (int c = 0; c < 4; c++) {
add_edge(N * 2 + 1 + c, N * 2 + 1 + (c + 1) % 4, Segment{corner[c], corner[(c + 1) % 4]});
}
V = N * 2 + 4;
for (int i = 1; i <= N; i++) {
add_edge(i * 2 - 1, i * 2, fence[i], true);
for (int j = i + 1; j <= N; j++) {
Segment A1A2 = Segment{fence[i].A, fence[j].A};
if (check(A1A2) == true) {
add_edge(i * 2 - 1, j * 2 - 1, A1A2);
}
Segment A1B2 = Segment{fence[i].A, fence[j].B};
if (check(A1B2) == true) {
add_edge(i * 2 - 1, j * 2, A1B2);
}
Segment B1A2 = Segment{fence[i].B, fence[j].A};
if (check(B1A2) == true) {
add_edge(i * 2, j * 2 - 1, B1A2);
}
Segment B1B2 = Segment{fence[i].B, fence[j].B};
if (check(B1B2) == true) {
add_edge(i * 2, j * 2, B1B2);
}
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i != j) {
Point P = project(fence[i].A, fence[j]);
Segment AP = Segment{fence[i].A, P};
if (is_inside(P, fence[j]) == true && check(AP) == true) {
add_edge(i * 2 - 1, j * 2 - 1, AP);
add_edge(i * 2 - 1, j * 2, AP);
}
Point Q = project(fence[i].B, fence[j]);
Segment BQ = Segment{fence[i].B, Q};
if (is_inside(Q, fence[j]) == true && check(BQ) == true) {
add_edge(i * 2, j * 2 - 1, BQ);
add_edge(i * 2, j * 2, BQ);
}
}
}
for (int c = 0; c < 4; c++) {
Segment AC = Segment{fence[i].A, corner[c]};
Segment BC = Segment{fence[i].B, corner[c]};
if (check(AC) == true) {
add_edge(i * 2 - 1, N * 2 + 1 + c, AC);
}
if (check(BC) == true) {
add_edge(i * 2, N * 2 + 1 + c, BC);
}
}
}
for (int u = 1; u <= V; u++) {
Point A = get_point(u);
Dijkstra(u);
}
cout << answer << "\n";
return 0;
}
Compilation message
fences.cpp: In function 'int main()':
fences.cpp:200:23: warning: narrowing conversion of 'S' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
200 | corner[0] = Point{S, S};
| ^
fences.cpp:200:26: warning: narrowing conversion of 'S' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
200 | corner[0] = Point{S, S};
| ^
fences.cpp:201:23: warning: narrowing conversion of '- S' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
201 | corner[1] = Point{-S, S};
| ^~
fences.cpp:201:27: warning: narrowing conversion of 'S' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
201 | corner[1] = Point{-S, S};
| ^
fences.cpp:202:23: warning: narrowing conversion of '- S' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
202 | corner[2] = Point{-S, -S};
| ^~
fences.cpp:202:27: warning: narrowing conversion of '- S' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
202 | corner[2] = Point{-S, -S};
| ^~
fences.cpp:203:23: warning: narrowing conversion of 'S' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
203 | corner[3] = Point{S, -S};
| ^
fences.cpp:203:26: warning: narrowing conversion of '- S' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
203 | corner[3] = Point{S, -S};
| ^~
fences.cpp:258:15: warning: variable 'A' set but not used [-Wunused-but-set-variable]
258 | Point A = get_point(u);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
500 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
500 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
500 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
