Submission #480538

#	Time	Username	Problem	Language	Result	Execution time	Memory
480538		rainboy	Zvijezda (COCI19_zvijezda)	C11	0 / 110	3 ms	332 KiB

zvijezda

#include <stdio.h>

#define N	2000

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

__int128 cross(long long x0, long long y0, long long x1, long long y1, long long x2, long long y2) {
	return (__int128) (x1 - x0) * (y2 - y0) - (__int128) (x2 - x0) * (y1 - y0);
}

long long cmp(long long x1, long long y1, long long x2, long long y2) {
	return x1 != x2 ? x1 - x2 : y1 - y2;
}

int main() {
	static int xx[N], yy[N], xxu[N], yyu[N], xxd[N], yyd[N];
	int n, nu, nd, q, online, i, i_, j, k;

	scanf("%d%d", &online, &n);
	i_ = -1;
	for (i = 0; i < n; i++) {
		scanf("%d%d", &xx[i], &yy[i]);
		if (i_ == -1 || cmp(xx[i_], yy[i_], xx[i], yy[i]) > 0)
			i_ = i;
	}
	nu = 0;
	for (j = 0; j < n; j++) {
		xxu[nu] = xx[(i_ - j + n) % n], yyu[nu] = yy[(i_ - j + n) % n], nu++;
		if (xx[(i_ - j + n) % n] >= xx[(i_ - j - 1 + n) % n])
			break;
	}
	nd = 0;
	for (j = 0; j < n; j++) {
		xxd[nd] = xx[(i_ + j) % n], yyd[nd] = yy[(i_ + j) % n], nd++;
		if (xx[(i_ + j) % n] > xx[(i_ + j + 1) % n])
			break;
	}
	scanf("%d", &q);
	k = 0;
	while (q--) {
		long long x, y;
		__int128 c;
		int lower, upper, lu, ru, ld, rd;

		scanf("%lld%lld", &x, &y);
		if (online)
			x ^= (long long) k * k * k, y ^= (long long) k * k * k;
		lower = -1, upper = nu - 1;
		while (upper - lower > 1) {
			i = (lower + upper) / 2, c = cross(x, y, xxu[i], yyu[i], xxu[i + 1], yyu[i + 1]);
			if (c == 0)
				goto da;
			if (cmp(xxu[i], yyu[i], x, y) <= 0 && c < 0)
				lower = i;
			else
				upper = i;
		}
		lu = upper;
		lower = 0, upper = nu;
		while (upper - lower > 1) {
			i = (lower + upper) / 2, c = cross(x, y, xxu[i], yyu[i], xxu[i - 1], yyu[i - 1]);
			if (c == 0)
				goto da;
			if (cmp(xxu[i], yyu[i], x, y) > 0 && c > 0)
				upper = i;
			else
				lower = i;
		}
		ru = lower;
		lower = -1, upper = nd - 1;
		while (upper - lower > 1) {
			i = (lower + upper) / 2, c = cross(x, -y, xxd[i], -yyd[i], xxd[i + 1], -yyd[i + 1]);
			if (c == 0)
				goto da;
			if (cmp(xxd[i], -yyd[i], x, -y) <= 0 && c < 0)
				lower = i;
			else
				upper = i;
		}
		ld = upper;
		lower = 0, upper = nd;
		while (upper - lower > 1) {
			i = (lower + upper) / 2, c = cross(x, -y, xxd[i], -yyd[i], xxd[i - 1], -yyd[i - 1]);
			if (c == 0)
				goto da;
			if (cmp(xxd[i], -yyd[i], x, -y) > 0 && c > 0)
				upper = i;
			else
				lower = i;
		}
		rd = lower;
		if (max(ru - lu, 0) + max(rd - ld, 0) >= n / 2) {
			printf("NE\n");
			continue;
		}
da:
		printf("DA\n"), k++;
	}
	return 0;
}

Compilation message (stderr)

zvijezda.c: In function 'main':
zvijezda.c:19:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  scanf("%d%d", &online, &n);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~
zvijezda.c:22:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
zvijezda.c:38:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
zvijezda.c:45:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%lld%lld", &x, &y);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60