답안 #486523

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
486523	2021-11-11T21:56:51 Z	rainboy	Relay (COI16_relay)	C	100 / 100	137 ms	9540 KB

relay

#include <stdio.h>

#define N	100000
#define M	100000

unsigned int X = 12345;

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

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

int xx[N + M], yy[N + M], xx_[N * 2], yy_[N * 2], idx[N * 2], n, m;

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

int compare1(int i, int j) {
	return xx[i] != xx[j] ? xx[i] - xx[j] : yy[i] - yy[j];
}

int compare2(int x1, int y1, int x2, int y2) {
	int sgn1 = x1 < 0 || x1 == 0 && y1 < 0 ? -1 : 1;
	int sgn2 = x2 < 0 || x2 == 0 && y2 < 0 ? -1 : 1;
	long long c;

	if (sgn1 != sgn2)
		return sgn1 - sgn2;
	c = cross2(x1, y1, x2, y2);
	return c == 0 ? 0 : (c > 0 ? -1 : 1);
}

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) {
			int c = compare2(xx_[ii[j]], yy_[ii[j]], xx_[i_], yy_[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 intersect(int l1, int r1, int l2, int r2) {
	int l1r1 = l1 <= r1, r1l2 = r1 < l2, l2r2 = l2 <= r2, r2l1 = r2 < l1;

	return !(l1r1 && r1l2 && l2r2 || r1l2 && l2r2 && r2l1 || l2r2 && r2l1 && l1r1 || r2l1 && l1r1 && r1l2);
}

int l, r;

void find_tangents(int o, int *p, int *q) {
	int lower, upper;

	if (compare1(o, n + l) < 0) {
		lower = -1, upper = (r - l + m) % m;
		while (upper - lower > 1) {
			int i = (lower + upper) / 2;

			if (cross(o, n + (l + i) % m, n + (l + i + 1) % m) >= 0)
				lower = i;
			else
				upper = i;
		}
		*p = (l + upper) % m;
		lower = -1, upper = (l - r + m) % m;
		while (upper - lower > 1) {
			int i = (lower + upper) / 2;

			if (cross(o, n + (l - i + m) % m, n + (l - (i + 1) + m) % m) <= 0)
				lower = i;
			else
				upper = i;
		}
		*q = (l - upper + m) % m;
	} else if (compare1(o, n + r) > 0) {
		lower = -1, upper = (l - r + m) % m;
		while (upper - lower > 1) {
			int i = (lower + upper) / 2;

			if (cross(o, n + (r + i) % m, n + (r + i + 1) % m) >= 0)
				lower = i;
			else
				upper = i;
		}
		*p = (r + upper) % m;
		lower = -1, upper = (r - l + m) % m;
		while (upper - lower > 1) {
			int i = (lower + upper) / 2;

			if (cross(o, n + (r - i + m) % m, n + (r - (i + 1) + m) % m) <= 0)
				lower = i;
			else
				upper = i;
		}
		*q = (r - upper + m) % m;
	} else if (cross(o, n + l, n + r) > 0) {
		lower = -1, upper = (r - l + m) % m;
		while (upper - lower > 1) {
			int i = (lower + upper) / 2;

			if (compare1(o, n + (r - i + m) % m) < 0 && cross(o, n + (r - i + m) % m, n + (r - (i + 1) + m) % m) > 0)
				lower = i;
			else
				upper = i;
		}
		*p = (r - upper + m) % m;
		lower = -1, upper = (r - l + m) % m;
		while (upper - lower > 1) {
			int i = (lower + upper) / 2;

			if (compare1(o, n + (l + i) % m) > 0 && cross(o, n + (l + i) % m, n + (l + i + 1) % m) < 0)
				lower = i;
			else
				upper = i;
		}
		*q = (l + upper) % m;
	} else {
		lower = -1, upper = (l - r + m) % m;
		while (upper - lower > 1) {
			int i = (lower + upper) / 2;

			if (compare1(o, n + (l - i + m) % m) > 0 && cross(o, n + (l - i + m) % m, n + (l - (i + 1) + m) % m) > 0)
				lower = i;
			else
				upper = i;
		}
		*p = (l - upper + m) % m;
		lower = -1, upper = (l - r + m) % m;
		while (upper - lower > 1) {
			int i = (lower + upper) / 2;

			if (compare1(o, n + (r + i) % m) < 0 && cross(o, n + (r + i) % m, n + (r + i + 1) % m) < 0)
				lower = i;
			else
				upper = i;
		}
		*q = (r + upper) % m;
	}
}

int main() {
	static int ii[N * 2], dd[N * 2 + 1];
	int n_, i, j, k;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	scanf("%d", &m);
	l = -1, r = -1;
	for (j = m - 1; j >= 0; j--) {
		scanf("%d%d", &xx[n + j], &yy[n + j]);
		if (l == -1 || compare1(n + l, n + j) > 0)
			l = j;
		if (r == -1 || compare1(n + r, n + j) < 0)
			r = j;
	}
	for (i = 0; i < n; i++) {
		int p, q;

		find_tangents(i, &p, &q);
		xx_[i << 1 | 0] = xx[i] - xx[n + p], yy_[i << 1 | 0] = yy[i] - yy[n + p];
		xx_[i << 1 | 1] = xx[n + q] - xx[i], yy_[i << 1 | 1] = yy[n + q] - yy[i];
	}
	for (i = 0; i < n * 2; i++)
		ii[i] = i;
	sort(ii, 0, n * 2);
	for (i = 0, n_ = 0; i < n * 2; i++)
		idx[ii[i]] = i + 1 == n * 2 || compare2(xx_[ii[i + 1]], yy_[ii[i + 1]], xx_[ii[i]], yy_[ii[i]]) != 0 ? n_++ : n_;
	for (i = 1; i < n; i++) {
		int l = idx[i << 1 | 0], r = idx[i << 1 | 1];

		if (intersect(idx[0 << 1 | 0], idx[0 << 1 | 1], l, r)) {
			if (l < r)
				dd[l]++, dd[r + 1]--;
			else
				dd[l]++, dd[n_]--, dd[0]++, dd[r + 1]--;
		}
	}
	for (i = 1; i < n_; i++)
		dd[i] += dd[i - 1];
	for (i = 0; i < n_; i++)
		if (dd[i] > 0)
			dd[i] = 1;
	for (i = 1; i < n_; i++)
		dd[i] += dd[i - 1];
	k = 0;
	for (i = 1; i < n; i++) {
		int l = idx[i << 1 | 0], r = idx[i << 1 | 1];

		if ((l < r ? dd[r] - (l == 0 ? 0 : dd[l - 1]) : dd[n_ - 1] - dd[l - 1] + dd[r]) > 0)
			k++;
	}
	printf("%d\n", k);
	return 0;
}

Compilation message

relay.c: In function 'compare2':
relay.c:27:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   27 |  int sgn1 = x1 < 0 || x1 == 0 && y1 < 0 ? -1 : 1;
      |                       ~~~~~~~~^~~~~~~~~
relay.c:28:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   28 |  int sgn2 = x2 < 0 || x2 == 0 && y2 < 0 ? -1 : 1;
      |                       ~~~~~~~~^~~~~~~~~
relay.c: In function 'intersect':
relay.c:62:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   62 |  return !(l1r1 && r1l2 && l2r2 || r1l2 && l2r2 && r2l1 || l2r2 && r2l1 && l1r1 || r2l1 && l1r1 && r1l2);
      |           ~~~~~~~~~~~~~^~~~~~~
relay.c:62:72: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   62 |  return !(l1r1 && r1l2 && l2r2 || r1l2 && l2r2 && r2l1 || l2r2 && r2l1 && l1r1 || r2l1 && l1r1 && r1l2);
      |                                                           ~~~~~~~~~~~~~^~~~~~~
relay.c:62:96: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   62 |  return !(l1r1 && r1l2 && l2r2 || r1l2 && l2r2 && r2l1 || l2r2 && r2l1 && l1r1 || r2l1 && l1r1 && r1l2);
      |                                                                                   ~~~~~~~~~~~~~^~~~~~~
relay.c: In function 'main':
relay.c:161:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
relay.c:163:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
relay.c:164:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |  scanf("%d", &m);
      |  ^~~~~~~~~~~~~~~
relay.c:167:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |   scanf("%d%d", &xx[n + j], &yy[n + j]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct

Subtask #2

19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	3 ms	588 KB	Output is correct
12	Correct	3 ms	528 KB	Output is correct
13	Correct	3 ms	460 KB	Output is correct
14	Correct	3 ms	460 KB	Output is correct
15	Correct	3 ms	460 KB	Output is correct
16	Correct	4 ms	460 KB	Output is correct
17	Correct	4 ms	460 KB	Output is correct
18	Correct	4 ms	460 KB	Output is correct
19	Correct	4 ms	460 KB	Output is correct
20	Correct	3 ms	460 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	77 ms	6824 KB	Output is correct
12	Correct	75 ms	6852 KB	Output is correct
13	Correct	70 ms	6876 KB	Output is correct
14	Correct	72 ms	6884 KB	Output is correct
15	Correct	111 ms	6864 KB	Output is correct
16	Correct	95 ms	6864 KB	Output is correct
17	Correct	94 ms	6924 KB	Output is correct
18	Correct	95 ms	6908 KB	Output is correct
19	Correct	99 ms	6860 KB	Output is correct
20	Correct	94 ms	6852 KB	Output is correct

Subtask #4

43.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	3 ms	588 KB	Output is correct
12	Correct	3 ms	528 KB	Output is correct
13	Correct	3 ms	460 KB	Output is correct
14	Correct	3 ms	460 KB	Output is correct
15	Correct	3 ms	460 KB	Output is correct
16	Correct	4 ms	460 KB	Output is correct
17	Correct	4 ms	460 KB	Output is correct
18	Correct	4 ms	460 KB	Output is correct
19	Correct	4 ms	460 KB	Output is correct
20	Correct	3 ms	460 KB	Output is correct
21	Correct	77 ms	6824 KB	Output is correct
22	Correct	75 ms	6852 KB	Output is correct
23	Correct	70 ms	6876 KB	Output is correct
24	Correct	72 ms	6884 KB	Output is correct
25	Correct	111 ms	6864 KB	Output is correct
26	Correct	95 ms	6864 KB	Output is correct
27	Correct	94 ms	6924 KB	Output is correct
28	Correct	95 ms	6908 KB	Output is correct
29	Correct	99 ms	6860 KB	Output is correct
30	Correct	94 ms	6852 KB	Output is correct
31	Correct	137 ms	8088 KB	Output is correct
32	Correct	122 ms	9540 KB	Output is correct
33	Correct	104 ms	8272 KB	Output is correct
34	Correct	107 ms	8308 KB	Output is correct
35	Correct	130 ms	8260 KB	Output is correct
36	Correct	128 ms	8244 KB	Output is correct
37	Correct	128 ms	8236 KB	Output is correct
38	Correct	137 ms	8260 KB	Output is correct
39	Correct	120 ms	7876 KB	Output is correct
40	Correct	120 ms	7856 KB	Output is correct