oj.uz

Submission #545141

# Submission time Handle Problem Language Result Execution time Memory
545141 2022-04-03T16:24:57 Z rainboy The Forest of Fangorn (CEOI14_fangorn) C
100 / 100
 814 ms 16204 KB 
#include <stdio.h>

#define N	2000
#define Q	10000

unsigned int X = 12345;

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

int xx[N + 1], yy[N + 1];

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

int o;

long long compare(int i, int j) {
	int x1 = xx[o] - xx[i], y1 = yy[o] - yy[i], x2 = xx[o] - xx[j], y2 = yy[o] - yy[j];
	int sgn1 = x1 < 0 || x1 == 0 && y1 < 0 ? -1 : 1, sgn2 = x2 < 0 || x2 == 0 && y2 < 0 ? -1 : 1;

	if (sgn1 != sgn2)
		return sgn1 - sgn2;
	return cross(x1, y1, x2, y2);
}

int inside(int i, int j, int k) {
	int x1 = xx[o] - xx[i], y1 = yy[o] - yy[i], x2 = xx[o] - xx[j], y2 = yy[o] - yy[j], x3 = xx[k] - xx[o], y3 = yy[k] - yy[o];

	return cross(x1, y1, x2, y2) < 0 ? cross(x1, y1, x3, y3) < 0 && cross(x3, y3, x2, y2) < 0 : cross(x1, y1, x3, y3) < 0 || cross(x3, y3, x2, y2) < 0;
}

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;
	}
}

int main() {
	static int xx_[Q], yy_[Q], ii[N][N], ii_[N];
	static char can[Q];
	int x_, y_, x, y, n, q, h, i, cnt;

	scanf("%d%d%d%d%d", &x_, &y_, &x, &y, &q);
	for (h = 0; h < q; h++)
		scanf("%d%d", &xx_[h], &yy_[h]);
	scanf("%d", &n), xx[n] = x, yy[n] = y;
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	for (o = 0; o < n; o++) {
		for (i = 0; i < n; i++)
			ii[o][i] = i;
		ii[o][0] = o, ii[o][o] = 0;
		sort(ii[o], 1, n);
		for (i = 1; i < n; i++)
			if (inside(ii[o][i], ii[o][i % (n - 1) + 1], n)) {
				ii_[o] = i;
				break;
			}
	}
	cnt = 0;
	for (h = 0; h < q; h++) {
		xx[n] = xx_[h], yy[n] = yy_[h];
		can[h] = 1, cnt++;
		for (o = 0; o < n; o++)
			if (!inside(ii[o][ii_[o]], ii[o][ii_[o] % (n - 1) + 1], n)) {
				can[h] = 0, cnt--;
				break;
			}
	}
	printf("%d\n", cnt);
	for (h = 0; h < q; h++)
		if (can[h])
			printf("%d ", h + 1);
	printf("\n");
	return 0;
}

Compilation message

fangorn.c: In function 'compare':
fangorn.c:22:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   22 |  int sgn1 = x1 < 0 || x1 == 0 && y1 < 0 ? -1 : 1, sgn2 = x2 < 0 || x2 == 0 && y2 < 0 ? -1 : 1;
      |                       ~~~~~~~~^~~~~~~~~
fangorn.c:22:76: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   22 |  int sgn1 = x1 < 0 || x1 == 0 && y1 < 0 ? -1 : 1, sgn2 = x2 < 0 || x2 == 0 && y2 < 0 ? -1 : 1;
      |                                                                    ~~~~~~~~^~~~~~~~~
fangorn.c: In function 'main':
fangorn.c:62:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%d%d%d%d%d", &x_, &y_, &x, &y, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.c:64:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   scanf("%d%d", &xx_[h], &yy_[h]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.c:65:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  scanf("%d", &n), xx[n] = x, yy[n] = y;
      |  ^~~~~~~~~~~~~~~
fangorn.c:67:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 260 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 556 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 548 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 5 ms 1108 KB Output is correct
11 Correct 5 ms 1236 KB Output is correct
12 Correct 5 ms 1236 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 146 ms 8208 KB Output is correct
5 Correct 30 ms 3020 KB Output is correct
6 Correct 586 ms 15972 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 15980 KB Output is correct
2 Correct 814 ms 16184 KB Output is correct
3 Correct 581 ms 16108 KB Output is correct
4 Correct 466 ms 16204 KB Output is correct