oj.uz

Submission #484303

# Submission time Handle Problem Language Result Execution time Memory
484303 2021-11-02T22:58:16 Z rainboy Planine (COCI21_planine) C
110 / 110
 280 ms 47556 KB 
#include <stdio.h>

#define N	1000000

unsigned int X = 12345;

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

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

int xx[N], yy[N];

long long cross(int i, int j, int k) {
	return cross2(xx[j] - xx[i], yy[j] - yy[i], xx[k] - xx[i], yy[k] - yy[i]);
}

long long pp[N], qq[N];

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 = cross2(pp[ii[j]], qq[ii[j]], pp[i_], qq[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 ll[N], rr[N], qu[N], ii[N];
	int n, y, i, k, cnt;
	long long p, q;

	scanf("%d%d", &n, &y);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	cnt = 0;
	for (i = 0; i < n; i++) {
		while (cnt >= 2 && cross(qu[cnt - 2], qu[cnt - 1], i) >= 0)
			cnt--;
		ll[i] = cnt ? qu[cnt - 1] : -1;
		qu[cnt++] = i;
	}
	cnt = 0;
	for (i = n - 1; i >= 0; i--) {
		while (cnt >= 2 && cross(qu[cnt - 2], qu[cnt - 1], i) <= 0)
			cnt--;
		rr[i] = cnt ? qu[cnt - 1] : -1;
		qu[cnt++] = i;
	}
	for (i = 2; i < n - 1; i += 2) {
		pp[i] = cross2(xx[ll[i]], yy[ll[i]] - y, xx[i] - xx[ll[i]], yy[i] - yy[ll[i]]);
		qq[i] = cross2(1, 0, xx[i] - xx[ll[i]], yy[i] - yy[ll[i]]);
		if (qq[i] < 0)
			pp[i] = -pp[i], qq[i] = -qq[i];
		pp[i + 1] = cross2(xx[rr[i]], yy[rr[i]] - y, xx[i] - xx[rr[i]], yy[i] - yy[rr[i]]);
		qq[i + 1] = cross2(1, 0, xx[i] - xx[rr[i]], yy[i] - yy[rr[i]]);
		if (qq[i + 1] < 0)
			pp[i + 1] = -pp[i + 1], qq[i + 1] = -qq[i + 1];
		ii[i / 2 - 1] = i + 1;
	}
	sort(ii, 0, n / 2 - 1);
	p = -1, q = 0, k = 0;
	for (i = 0; i < n / 2 - 1; i++)
		if (cross2(p, q, pp[ii[i] - 1], qq[ii[i] - 1]) < 0)
			p = pp[ii[i]], q = qq[ii[i]], k++;
	printf("%d\n", k);
	return 0;
}

Compilation message

Main.c: In function 'main':
Main.c:50:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |  scanf("%d%d", &n, &y);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 3 ms 688 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 22 ms 4584 KB Output is correct
5 Correct 22 ms 4784 KB Output is correct
6 Correct 24 ms 4940 KB Output is correct
7 Correct 220 ms 43520 KB Output is correct
8 Correct 231 ms 45680 KB Output is correct
9 Correct 245 ms 47368 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 288 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 3 ms 688 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 22 ms 4584 KB Output is correct
5 Correct 22 ms 4784 KB Output is correct
6 Correct 24 ms 4940 KB Output is correct
7 Correct 220 ms 43520 KB Output is correct
8 Correct 231 ms 45680 KB Output is correct
9 Correct 245 ms 47368 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 288 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 288 KB Output is correct
17 Correct 237 ms 44552 KB Output is correct
18 Correct 238 ms 44444 KB Output is correct
19 Correct 24 ms 4740 KB Output is correct
20 Correct 234 ms 43636 KB Output is correct
21 Correct 24 ms 4556 KB Output is correct
22 Correct 252 ms 47396 KB Output is correct
23 Correct 0 ms 332 KB Output is correct
24 Correct 235 ms 46532 KB Output is correct
25 Correct 23 ms 4684 KB Output is correct
26 Correct 280 ms 47556 KB Output is correct
27 Correct 12 ms 2528 KB Output is correct