Submission #678863

#	Time	Username	Problem	Language	Result	Execution time	Memory
678863		rainboy	Fences (JOI18_fences)	C++17	100 / 100	14 ms	628 KiB

fences

#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 (stderr)

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]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 33 / 33
• Subtask 3: 49 / 49