Submission #894726

#	Time	Username	Problem	Language	Result	Execution time	Memory
894726		rainboy	공룡 발자국 (KOI18_footprint)	C11	100 / 100	1236 ms	71264 KiB

footprint

#include <stdio.h>

#define N	3000

int max(int a, int b) { return a > b ? a : b; }

unsigned int Z = 12345;

int rand_() {
	return (Z *= 3) >> 1;
}

int xx[N], yy[N];

long long cross(int i, int j, int k) {
	return (long long) (xx[j] - xx[i]) * (yy[k] - yy[i]) - (long long) (xx[k] - xx[i]) * (yy[j] - yy[i]);
}

int o;

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k) {
			long long c = cross(o, ii[j], i_);

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

int main() {
	static int hh[N], ii[N], jj[N], dp[N][N], dq[N][N];
	int n, ml, mr, h, h_, i, i0, i_, j, j_, x;

	scanf("%d", &n);
	i0 = -1;
	for (i = 0; i < n; i++) {
		scanf("%d%d", &xx[i], &yy[i]);
		if (i0 == -1 || yy[i0] > yy[i])
			i0 = i;
	}
	for (i = 0; i < n; i++)
		ii[i] = i;
	ii[0] = i0, ii[i0] = 0;
	o = i0, sort(ii, 1, n);
	for (i = 1; i < n; i++) {
		i_ = ii[i];
		ml = 0;
		for (h = 1; h < i; h++)
			if (cross(i0, ii[h], i_) < 0)
				hh[ml++] = ii[h];
		o = i_, sort(hh, 0, ml);
		mr = 0;
		for (j = i + 1; j < n; j++)
			if (cross(i0, i_, ii[j]) < 0)
				jj[mr++] = ii[j];
		o = i_, sort(jj, 0, mr);
		h = 0, j = 0, x = 0;
		while (j < mr) {
			h_ = h == ml ? -1 : hh[h], j_ = jj[j];
			if (h < ml && cross(h_, i_, j_) < 0)
				x = max(x, dq[h_][i_]), h++;
			else
				dp[i_][j_] = x, j++;
		}
		h = ml - 1, j = mr - 1, x = -1;
		while (j >= 0) {
			h_ = h < 0 ? -1 : hh[h], j_ = jj[j];
			if (h >= 0 && cross(h_, i_, j_) > 0)
				x = max(x, dp[h_][i_]), h--;
			else
				dq[i_][j_] = x + 1, j--;
		}
	}
	x = 0;
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			x = max(x, dq[i][j]);
	if (x == 0) {
		printf("0\n");
		return 0;
	}
	printf("%d\n", (x + 1) * 2);
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			if (dq[i][j] == x)
				goto out;
out:
	printf("%d %d\n", xx[i0], yy[i0]);
	printf("%d %d\n", xx[j], yy[j]);
	printf("%d %d\n", xx[i], yy[i]);
	while (1) {
		for (h = 0; h < n; h++)
			if (cross(i0, h, i) < 0 && cross(h, i, j) > 0 && dq[i][j] == dp[h][i] + 1) {
				printf("%d %d\n", xx[h], yy[h]);
				j = i, i = h;
				break;
			}
		if (dp[i][j] == 0)
			break;
		for (h = 0; h < n; h++)
			if (cross(i0, h, i) < 0 && cross(h, i, j) < 0 && dp[i][j] == dq[h][i]) {
				printf("%d %d\n", xx[h], yy[h]);
				j = i, i = h;
				break;
			}
	}
	return 0;
}

Compilation message (stderr)

footprint.c: In function 'main':
footprint.c:47:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
footprint.c:50:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 12 / 12
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45