| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 678862 | rainboy | Fences (JOI18_fences) | C11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}