Submission #480540

#	Time	Username	Problem	Language	Result	Execution time	Memory
480540		rainboy	Zvijezda (COCI19_zvijezda)	C11	110 / 110	149 ms	7972 KiB

zvijezda

#include <stdio.h>

#define N	100000

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++) {
		int p = (i_ - j + n) % n, q = (i_ - (j + 1) + n) % n;

		xxu[nu] = xx[p], yyu[nu] = yy[p], nu++;
		if (cmp(xx[p], yy[p], xx[q], yy[q]) > 0)
			break;
	}
	nd = 0;
	for (j = 0; j < n; j++) {
		int p = (i_ + j) % n, q = (i_ + (j + 1)) % n;

		xxd[nd] = xx[p], yyd[nd] = yy[p], nd++;
		if (cmp(xx[p], yy[p], xx[q], yy[q]) > 0)
			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:42:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
zvijezda.c:49:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   scanf("%lld%lld", &x, &y);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~

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