답안 #678862

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
678862 2023-01-06T18:45:35 Z rainboy Fences (JOI18_fences) C
컴파일 오류
0 ms 0 KB
#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.c: In function 'intersect':
fences.c:35:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   35 |  return a < eps && b < -eps || a < -eps && b < eps;
      |                 ^
fences.c: In function 'main':
fences.c:80:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  scanf("%d%d", &n, &s), n += 4;
      |  ^~~~~~~~~~~~~~~~~~~~~
fences.c:86:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccj60ZRh.o: in function `add':
fences.c:(.text+0x54d): undefined reference to `hypot'
collect2: error: ld returned 1 exit status