oj.uz

Submission #480540

# Submission time Handle Problem Language Result Execution time Memory
480540 2021-10-16T20:29:22 Z rainboy Zvijezda (COCI19_zvijezda) C
110 / 110
 149 ms 7972 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 2 ms 320 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 2 ms 320 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 67 ms 636 KB Output is correct
13 Correct 82 ms 540 KB Output is correct
14 Correct 97 ms 4480 KB Output is correct
15 Correct 104 ms 5040 KB Output is correct
16 Correct 136 ms 7476 KB Output is correct
17 Correct 134 ms 7388 KB Output is correct
18 Correct 83 ms 4420 KB Output is correct
19 Correct 102 ms 5212 KB Output is correct
20 Correct 122 ms 6172 KB Output is correct
21 Correct 134 ms 7420 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 1984 KB Output is correct
2 Correct 149 ms 7940 KB Output is correct
3 Correct 106 ms 5176 KB Output is correct
4 Correct 140 ms 7972 KB Output is correct
5 Correct 135 ms 7876 KB Output is correct
6 Correct 128 ms 7376 KB Output is correct
7 Correct 133 ms 7500 KB Output is correct
8 Correct 141 ms 7920 KB Output is correct
9 Correct 140 ms 7248 KB Output is correct