Submission #548850

#	Time	Username	Problem	Language	Result	Execution time	Memory
548850		rainboy	Printed Circuit Board (CEOI12_circuit)	C11	85 / 100	31 ms	1096 KiB

circuit

#include <assert.h>
#include <stdio.h>

#define N	200000

long long cross(int x1, int y1, int x2, int y2) {
	return (long long) x1 * y2 - (long long) x2 * y1;
}

int xx[N], yy[N], n;

long long cross2(int i, int j) {
	i %= n, j %= n;
	return cross(xx[i], yy[i], xx[j], yy[j]);
}

long long cross3(int i, int j, int k) {
	i %= n, j %= n, k %= n;
	return cross(xx[j] - xx[i], yy[j] - yy[i], xx[k] - xx[i], yy[k] - yy[i]);
}

int compare(int i, int j) {
	int i0 = i, i1 = i + 1, j0 = j, j1 = j + 1, tmp;
	long long c0, c1;

	if (cross2(i0, i1) > 0)
		tmp = i0, i0 = i1, i1 = tmp;
	if (cross2(j0, j1) > 0)
		tmp = j0, j0 = j1, j1 = tmp;
	c0 = cross3(i0, i1, j0), c1 = cross3(i0, i1, j1);
	if (c0 >= 0 && c1 >= 0)
		return -1;
	if (c0 <= 0 && c1 <= 0)
		return 1;
	c0 = cross3(j0, j1, i0), c1 = cross3(j0, j1, i1);
	if (c0 >= 0 && c1 >= 0)
		return 1;
	if (c0 <= 0 && c1 <= 0)
		return -1;
	return 0;
}

int main() {
	static int ii1[N], jj1[N], ii2[N], jj2[N];
	static char visible[N];
	int h, i, j, l, cnt1, cnt2, cnt;

	scanf("%d", &n);
	assert(n <= 190000);
	l = -1;
	for (i = 0; i < n; i++) {
		scanf("%d%d", &xx[i], &yy[i]);
		if (l == -1 || cross2(l, i) > 0)
			l = i;
	}
	i = l;
	cnt1 = cnt2 = 0;
	for (j = l; j < l + n; j++) {
		long long c = cross2(j, j + 1);

		if (c == 0) {
			if (cross2(i, j) == 0 && xx[i % n] > xx[(j + 1) % n])
				i = j + 1;
		} else if (c < 0) {
			if (cross2(j, i) <= 0 && cross2(i, j + 1) < 0)
				while (1) {
					if (cnt2 == 0) {
						ii1[cnt1] = i, jj1[cnt1] = j, cnt1++;
						i = j + 1;
						break;
					}
					if (compare(jj2[cnt2 - 1], j) <= 0)
						break;
					if (cross2(j + 1, ii2[cnt2 - 1]) < 0) {
						ii1[cnt1] = i, jj1[cnt1] = j, cnt1++;
						i = j + 1;
						break;
					}
					cnt2--;
					if (cross3(j, j + 1, ii2[cnt2]) <= 0) {
						ii1[cnt1] = i, jj1[cnt1] = j, cnt1++;
						i = ii2[cnt2];
						break;
					}
				}
		} else {
			if (cross2(j, i) >= 0 && cross2(i, j + 1) > 0) {
				while (1) {
					if (cnt1 == 0) {
						ii2[cnt2] = i, jj2[cnt2] = j, cnt2++;
						i = j + 1;
						break;
					}
					if (compare(jj1[cnt1 - 1], j) <= 0)
						break;
					if (cross2(j + 1, ii1[cnt1 - 1]) > 0) {
						ii2[cnt2] = i, jj2[cnt2] = j, cnt2++;
						i = j + 1;
						break;
					}
					cnt1--;
					if (cross3(j, j + 1, ii1[cnt1]) >= 0) {
						ii2[cnt2] = i, jj2[cnt2] = j, cnt2++;
						i = ii1[cnt1];
						break;
					}
				}
			}
		}
	}
	visible[i % n] = 1;
	for (h = 0; h < cnt1; h++)
		visible[ii1[h] % n] = 1;
	for (h = 0; h < cnt2; h++)
		visible[ii2[h] % n] = 1;
	cnt = 0;
	for (i = 0; i < n; i++)
		if (visible[i])
			cnt++;
	printf("%d\n", cnt);
	for (i = 0; i < n; i++)
		if (visible[i])
			printf("%d ", i + 1);
	printf("\n");
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 85 / 100