Submission #924361

#	Time	Username	Problem	Language	Result	Execution time	Memory
924361		rainboy	레이저 센서 (KOI16_laser)	C11	100 / 100	166 ms	860 KiB

laser

/* https://math.stackexchange.com/questions/4650848/prove-that-if-2n-points-are-colored-red-or-blue-then-we-can-always-connect-th */
#include <stdio.h>
#include <string.h>

#define N	1000

unsigned int Z = 12345;

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

int xx[N * 4], yy[N * 4], uu[N], vv[N], n, o;

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 compare(int i, int j) {
	long long c;

	if (xx[i] == xx[j] && yy[i] == yy[j])
		return 0;
	if (xx[i] == xx[o] && yy[i] == yy[o])
		return -1;
	if (xx[j] == xx[o] && yy[j] == yy[o])
		return 1;
	c = cross(o, i, j);
	return c < 0 ? -1 : 1;
}

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 = compare(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;
	}
}

void solve(int *ii, int m) {
	int h, h_, i, j, tmp, d;

	if (m == 2) {
		if (ii[0] >= n * 2)
			tmp = ii[0], ii[0] = ii[1], ii[1] = tmp;
		i = ii[0] >> 1, j = ii[1] - n * 2;
		if (uu[i] == -1)
			uu[i] = j;
		else
			vv[i] = j;
		return;
	}
	h_ = -1;
	for (h = 0; h < m; h++)
		if (h_ == -1 || xx[ii[h_]] > xx[ii[h]] || xx[ii[h_]] == xx[ii[h]] && yy[ii[h_]] > yy[ii[h]])
			h_ = h;
	o = ii[h_];
	tmp = ii[0], ii[0] = ii[h_], ii[h_] = tmp;
	sort(ii, 1, m);
	d = ii[0] < n * 2 ? 1 : -1;
	for (h = 1; h + 1 < m; h++)
		if ((d += ii[h] < n * 2 ? 1 : -1) == 0) {
			solve(ii, h + 1), solve(ii + h + 1, m - h - 1);
			return;
		}
	tmp = ii[1], ii[1] = ii[m - 1], ii[m - 1] = tmp;
	solve(ii, 2), solve(ii + 2, m - 2);
}

int main() {
	static int ii[N * 4];
	int i, x, y;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d%d", &x, &y);
		xx[i << 1 | 0] = x, yy[i << 1 | 0] = y;
		xx[i << 1 | 1] = x, yy[i << 1 | 1] = y;
	}
	for (i = 0; i < n * 2; i++)
		scanf("%d%d", &xx[n * 2 + i], &yy[n * 2 + i]);
	for (i = 0; i < n * 4; i++)
		ii[i] = i;
	memset(uu, -1, n * sizeof *uu), memset(vv, -1, n * sizeof *vv);
	solve(ii, n * 4);
	for (i = 0; i < n; i++)
		printf("%d %d\n", uu[i] + 1, vv[i] + 1);
	return 0;
}

Compilation message (stderr)

laser.c: In function 'solve':
laser.c:69:69: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   69 |   if (h_ == -1 || xx[ii[h_]] > xx[ii[h]] || xx[ii[h_]] == xx[ii[h]] && yy[ii[h_]] > yy[ii[h]])
      |                                             ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
laser.c: In function 'main':
laser.c:88:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
laser.c:90:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |   scanf("%d%d", &x, &y);
      |   ^~~~~~~~~~~~~~~~~~~~~
laser.c:95:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |   scanf("%d%d", &xx[n * 2 + i], &yy[n * 2 + i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 19 / 19
• Subtask 3: 33 / 33
• Subtask 4: 34 / 34