#include <math.h>
#include <stdio.h>
#define N 104
#define INF 1e9
#define eps 1e-9
double abs_(double a) { return a > 0 ? a : -a; }
double min(double a, double b) { return a < b ? a : b; }
double max(double a, double b) { return a > b ? a : b; }
double cross2(double x1, double y1, double x2, double y2) {
return x1 * y2 - x2 * y1;
}
double cross(double x0, double y0, double x1, double y1, double x2, double y2) {
return cross2(x1 - x0, y1 - y0, x2 - x0, y2 - y0);
}
double dot2(double x1, double y1, double x2, double y2) {
return x1 * x2 + y1 * y2;
}
double dot(double x0, double y0, double x1, double y1, double x2, double y2) {
return dot2(x1 - x0, y1 - y0, x2 - x0, y2 - y0);
}
int intersect(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) {
double a, b;
if (abs_(cross2(x2 - x1, y2 - y1, x4 - x3, y4 - y3)) < eps)
return 0;
a = cross(x1, y1, x3, y3, x4, y4) * cross(x2, y2, x3, y3, x4, y4);
b = cross(x3, y3, x1, y1, x2, y2) * cross(x4, y4, x1, y1, x2, y2);
return a < eps && b < -eps || a < -eps && b < eps;
}
int hit(double x1, double y1, double x2, double y2) {
double tmp;
if (y1 < y2)
tmp = x1, x1 = x2, x2 = tmp, tmp = y1, y1 = y2, y2 = tmp;
return y1 > 0 && y2 <= 0 && cross2(x1, y1, x2, y2) < 0;
}
int xx[N * 2], yy[N * 2], n, s; double dd[N * 2][N * 2];
void add(int i, int j, int x0, int y0, int x1, int y1, int x2, int y2) {
double t, x3, y3, d;
int i0, j0, i1, j1, c;
t = min(max(dot(x1, y1, x0, y0, x2, y2) / dot(x1, y1, x2, y2, x2, y2), 0), 1);
x3 = x1 + (x2 - x1) * t, y3 = y1 + (y2 - y1) * t;
if (intersect(x0, y0, x3, y3, -s, -s, -s, s))
return;
if (intersect(x0, y0, x3, y3, -s, s, s, s))
return;
if (intersect(x0, y0, x3, y3, s, s, s, -s))
return;
if (intersect(x0, y0, x3, y3, s, -s, -s, -s))
return;
if (abs_((x0 + x3) / 2) <= s - eps && abs_((y0 + y3) / 2) <= s - eps)
return;
i0 = i << 1, i1 = i0 | 1, j0 = j << 1, j1 = j0 | 1;
d = hypot(x3 - x0, y3 - y0);
c = hit(xx[i0], yy[i0], x0, y0) ^ hit(x0, y0, x3, y3) ^ hit(x3, y3, xx[j0], yy[j0]);
if (c == 0) {
dd[i0][j0] = min(dd[i0][j0], d), dd[j0][i0] = min(dd[j0][i0], d);
dd[i1][j1] = min(dd[i1][j1], d), dd[j1][i1] = min(dd[j1][i1], d);
} else {
dd[i0][j1] = min(dd[i0][j1], d), dd[j1][i0] = min(dd[j1][i0], d);
dd[i1][j0] = min(dd[i1][j0], d), dd[j0][i1] = min(dd[j0][i1], d);
}
}
int main() {
int i, j, k;
double ans;
scanf("%d%d", &n, &s), n += 4;
xx[0] = -s, yy[0] = -s, xx[1] = -s, yy[1] = -s;
xx[2] = -s, yy[2] = s, xx[3] = -s, yy[3] = s;
xx[4] = s, yy[4] = -s, xx[5] = s, yy[5] = -s;
xx[6] = s, yy[6] = s, xx[7] = s, yy[7] = s;
for (i = 8; i < n * 2; i++)
scanf("%d%d", &xx[i], &yy[i]);
for (i = 0; i < n * 2; i++)
for (j = 0; j < n * 2; j++)
dd[i][j] = i == j ? 0 : INF;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (i != j) {
add(i, j, xx[i << 1 | 0], yy[i << 1 | 0], xx[j << 1 | 0], yy[j << 1 | 0], xx[j << 1 | 1], yy[j << 1 | 1]);
add(i, j, xx[i << 1 | 1], yy[i << 1 | 1], xx[j << 1 | 0], yy[j << 1 | 0], xx[j << 1 | 1], yy[j << 1 | 1]);
}
for (k = 0; k < n * 2; k++)
for (i = 0; i < n * 2; i++)
for (j = 0; j < n * 2; j++)
dd[i][j] = min(dd[i][j], dd[i][k] + dd[k][j]);
ans = INF;
for (i = 0; i < n; i++)
ans = min(ans, dd[i << 1 | 0][i << 1 | 1]);
printf("%.10f\n", ans);
return 0;
}
Compilation message
fences.cpp: In function 'int intersect(double, double, double, double, double, double, double, double)':
fences.cpp:35:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
35 | return a < eps && b < -eps || a < -eps && b < eps;
| ^
fences.cpp: In function 'int main()':
fences.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%d%d", &n, &s), n += 4;
| ~~~~~^~~~~~~~~~~~~~~~
fences.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | scanf("%d%d", &xx[i], &yy[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
288 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
284 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
288 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
288 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
284 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
288 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
288 KB |
Output is correct |
23 |
Correct |
1 ms |
284 KB |
Output is correct |
24 |
Correct |
1 ms |
292 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
0 ms |
212 KB |
Output is correct |
29 |
Correct |
0 ms |
212 KB |
Output is correct |
30 |
Correct |
0 ms |
212 KB |
Output is correct |
31 |
Correct |
0 ms |
212 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
33 |
Correct |
0 ms |
288 KB |
Output is correct |
34 |
Correct |
1 ms |
212 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
0 ms |
212 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Correct |
0 ms |
212 KB |
Output is correct |
39 |
Correct |
0 ms |
212 KB |
Output is correct |
40 |
Correct |
0 ms |
212 KB |
Output is correct |
41 |
Correct |
1 ms |
212 KB |
Output is correct |
42 |
Correct |
0 ms |
212 KB |
Output is correct |
43 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
288 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
284 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
288 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
288 KB |
Output is correct |
23 |
Correct |
1 ms |
284 KB |
Output is correct |
24 |
Correct |
1 ms |
292 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
0 ms |
212 KB |
Output is correct |
29 |
Correct |
0 ms |
212 KB |
Output is correct |
30 |
Correct |
0 ms |
212 KB |
Output is correct |
31 |
Correct |
0 ms |
212 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
33 |
Correct |
0 ms |
288 KB |
Output is correct |
34 |
Correct |
1 ms |
212 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
0 ms |
212 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Correct |
0 ms |
212 KB |
Output is correct |
39 |
Correct |
0 ms |
212 KB |
Output is correct |
40 |
Correct |
0 ms |
212 KB |
Output is correct |
41 |
Correct |
1 ms |
212 KB |
Output is correct |
42 |
Correct |
0 ms |
212 KB |
Output is correct |
43 |
Correct |
1 ms |
212 KB |
Output is correct |
44 |
Correct |
11 ms |
620 KB |
Output is correct |
45 |
Correct |
9 ms |
624 KB |
Output is correct |
46 |
Correct |
9 ms |
624 KB |
Output is correct |
47 |
Correct |
9 ms |
596 KB |
Output is correct |
48 |
Correct |
10 ms |
628 KB |
Output is correct |
49 |
Correct |
9 ms |
596 KB |
Output is correct |
50 |
Correct |
10 ms |
596 KB |
Output is correct |
51 |
Correct |
10 ms |
596 KB |
Output is correct |
52 |
Correct |
14 ms |
624 KB |
Output is correct |
53 |
Correct |
10 ms |
548 KB |
Output is correct |
54 |
Correct |
10 ms |
624 KB |
Output is correct |
55 |
Correct |
9 ms |
596 KB |
Output is correct |
56 |
Correct |
9 ms |
540 KB |
Output is correct |
57 |
Correct |
9 ms |
596 KB |
Output is correct |
58 |
Correct |
9 ms |
620 KB |
Output is correct |
59 |
Correct |
9 ms |
596 KB |
Output is correct |
60 |
Correct |
9 ms |
596 KB |
Output is correct |
61 |
Correct |
10 ms |
596 KB |
Output is correct |
62 |
Correct |
1 ms |
340 KB |
Output is correct |
63 |
Correct |
0 ms |
340 KB |
Output is correct |
64 |
Correct |
8 ms |
620 KB |
Output is correct |
65 |
Correct |
9 ms |
628 KB |
Output is correct |
66 |
Correct |
8 ms |
596 KB |
Output is correct |
67 |
Correct |
8 ms |
596 KB |
Output is correct |
68 |
Correct |
8 ms |
520 KB |
Output is correct |
69 |
Correct |
9 ms |
596 KB |
Output is correct |
70 |
Correct |
8 ms |
608 KB |
Output is correct |
71 |
Correct |
9 ms |
624 KB |
Output is correct |
72 |
Correct |
9 ms |
596 KB |
Output is correct |