#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ld, ld> pdd;
const int MAXN = 408;
const ld inf = 1e6;
const ld eps = 1e-9;
ld dist[MAXN][MAXN];
int n, s;
pii r1(0, 0);
pii r2(1000,999);
int dot(pii a, pii b) {
return a.first*b.first+a.second*b.second;
}
pdd operator*(ld v, pii a) {
return pdd(a.first*v, a.second*v);
}
ld mag(pdd a) {
return sqrt(a.first*a.first+a.second*a.second);
}
ld mag(pii a) {
return sqrt(a.first*a.first+a.second*a.second);
}
pii operator-(pii a, pii b) {
return pii(a.first-b.first, a.second-b.second);
}
pii operator+(pii a, pii b) {
return pii(a.first+b.first, a.second+b.second);
}
pii rot(pii a) { // 90* cc
return pii(-a.second, a.first);
}
pdd operator-(pdd a, pdd b) {
return pdd(a.first-b.first, a.second-b.second);
}
pdd operator+(pdd a, pdd b) {
return pdd(a.first+b.first, a.second+b.second);
}
int operator*(pii a, pii b) {
return a.first*b.second-a.second*b.first;
}
ld operator*(pdd a, pdd b) {
return a.first*b.second-a.second*b.first;
}
int sign(int a) {
if (a > 0) return 1;
if (a == 0) return 0;
return -1;
}
int sign(ld a) {
if (a > eps) return 1;
if (a < eps) return -1;
return 0;
}
map<pii, int> nodes;
pii points[MAXN];
int hsh(int i, bool b) {
return 2*i+b;
}
void add(pii p) {
if (nodes.find(p) == nodes.end()) {
int a = nodes.size();
nodes[p] = a;
points[a] = p;
}
}
bool intersect_single(pii a, pii b, pii c, pii d) {
return sign((c-a)*(b-a))*sign((d-a)*(b-a)) <= 0;
}
bool single_strict(pdd a, pdd b, pdd c, pdd d) {
return ((c-a)*(b-a))*((d-a)*(b-a)) < -eps;
}
bool intersect(pii a, pii b, pii c, pii d) {
return intersect_single(a, b, c, d) && intersect_single(c, d, a, b);
}
bool intersect_strict(pdd a, pdd b, pdd c, pdd d) {
return single_strict(a, b, c, d) && single_strict(c, d, a, b);
}
bool contained(pdd a) {
return (-s+eps < a.first && a.first < s-eps && -s+eps < a.second && a.second < s-eps);
}
bool valid(pdd a, pdd b) {
if (contained(0.5*(a+b))) return 0;
for (int i = 0; i < 4; i++) {
if (intersect_strict((pdd)points[i], (pdd)points[(i+1)%4], a, b)) return 0;
}
return 1;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> s;
int m = 4*n+8;
add(pii(-s, -s));
add(pii(s, -s));
add(pii(s, s));
add(pii(-s, s));
for (int i = 0; i < m; i++) {
fill(dist[i], dist[i]+m, inf);
}
vector<pii> lines;
for (int i = 0; i < n; i++) {
pii p1, p2;
cin >> p1.first >> p1.second >> p2.first >> p2.second;
add(p1); add(p2);
int a = nodes[p1], b = nodes[p2];
lines.push_back(pii(a, b));
bool rev = intersect(r1, r2, p1, p2);
dist[2*a][2*b^rev] = 0;
dist[2*b^rev][2*a] = 0;
dist[2*a+1][2*b^1^rev] = 0;
dist[2*b^1^rev][2*a+1] = 0;
}
m = 2*nodes.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < nodes.size(); j++) {
if (lines[i].first == j || lines[i].second == j) continue;
pii p1 = points[lines[i].first], p2 = points[lines[i].second], p3 = points[j];
pii p4 = p3+rot(p2-p1);
if (intersect_single(p3, p4, p1, p2)) {
ld curdist = (ld)((p3-p1)*(p2-p1))/dot(p2-p1, p2-p1); // this is actually dist/mag(p2-p1)
pdd inter = curdist*rot(p2-p1)+(pdd)p3;
if (valid((pdd)p3, inter)) {
curdist = abs(curdist*mag(p2-p1));
bool rev = intersect_strict(r1, r2, p3, p1);
dist[2*j][2*lines[i].first^rev] = dist[2*lines[i].first^rev][2*j] = min(curdist, dist[2*j][2*lines[i].first^rev]);
dist[2*j^1][2*lines[i].first^1^rev] = dist[2*lines[i].first^1^rev][2*j^1] = min(curdist, dist[2*j^1][2*lines[i].first^1^rev]);
}
}
}
}
for (int i = 0; i < m/2; i++) {
dist[2*i][2*i] = dist[2*i+1][2*i+1] = 0;
for (int j = i+1; j < m/2; j++) {
if (valid((pdd)points[i], (pdd)points[j])) {
ld curdist = mag(points[j]-points[i]);
bool rev = intersect(points[i], points[j], r1, r2);
dist[2*i][2*j^rev] = dist[2*j^rev][2*i] = min(dist[2*i][2*j^rev], curdist);
dist[2*i^1][2*j^1^rev] = dist[2*j^1^rev][2*i^1] = min(dist[2*i^1][2*j^1^rev], curdist);
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < m; k++) {
dist[j][k] = min(dist[j][k], dist[j][i]+dist[i][k]);
}
}
}
ld ans = inf;
for (int i = 0; i < m/2; i++) {
ans = min(ans, dist[2*i][2*i+1]);
}
// for (int i = 0; i < m/2; i++) {
// if (abs(ans-dist[2*i][2*i+1]) < eps) cout << points[i].first << " " << points[i].second << "\n";
// }
cout << fixed << setprecision(10) << ans << "\n";
}
Compilation message
fences.cpp: In function 'int main()':
fences.cpp:142:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<std::pair<int, int>, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for (int j = 0; j < nodes.size(); j++) {
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
336 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
344 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
336 KB |
Output is correct |
| 16 |
Correct |
1 ms |
336 KB |
Output is correct |
| 17 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
336 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
344 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
336 KB |
Output is correct |
| 16 |
Correct |
1 ms |
336 KB |
Output is correct |
| 17 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
336 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
344 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
336 KB |
Output is correct |
| 16 |
Correct |
1 ms |
336 KB |
Output is correct |
| 17 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
