oj.uz

답안 #486440

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
486440 2021-11-11T16:50:20 Z rainboy Relay (COI16_relay) C
37 / 100
 2000 ms 2792 KB 
#include <stdio.h>

#define N	100000
#define M	100000

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

long long cross(int x0, int y0, int x1, int y1, int x2, int y2) {
	return cross2(x1 - x0, y1 - y0, x2 - x0, y2 - y0);
}

int xx[N + M], yy[N + M], xxl[N], yyl[N], xxr[N], yyr[N];

int compare(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);
}

int visible(int i1, int i2) {
	int xl1 = xxl[i1], yl1 = yyl[i1], xr1 = xxr[i1], yr1 = yyr[i1];
	int xl2 = xxl[i2], yl2 = yyl[i2], xr2 = xxr[i2], yr2 = yyr[i2];
	int l1r1 = compare(xl1, yl1, xr1, yr1) <= 0;
	int r1l2 = compare(xr1, yr1, xl2, yl2) < 0;
	int l2r2 = compare(xl2, yl2, xr2, yr2) <= 0;
	int r2l1 = compare(xr2, yr2, xl1, yl1) < 0;

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

int main() {
	static char good[N];
	int n, m, i, i1, i2, j, p, q, k;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	scanf("%d", &m);
	for (j = 0; j < m; j++)
		scanf("%d%d", &xx[n + j], &yy[n + j]);
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++) {
			p = (j - 1 + m) % m, q = (j + 1) % m;
			if (cross(xx[i], yy[i], xx[n + p], yy[n + p], xx[n + j], yy[n + j]) >= 0
					&& cross(xx[i], yy[i], xx[n + q], yy[n + q], xx[n + j], yy[n + j]) > 0)
				xxl[i] = xx[i] - xx[n + j], yyl[i] = yy[i] - yy[n + j];
			if (cross(xx[i], yy[i], xx[n + q], yy[n + q], xx[n + j], yy[n + j]) <= 0
					&& cross(xx[i], yy[i], xx[n + p], yy[n + p], xx[n + j], yy[n + j]) < 0)
				xxr[i] = xx[n + j] - xx[i], yyr[i] = yy[n + j] - yy[i];
		}
	for (i1 = 1; i1 < n; i1++)
		if (visible(0, i1)) {
			good[i1] = 1;
			for (i2 = 1; i2 < n; i2++)
				if (visible(i1, i2))
					good[i2] = 1;
		}
	k = 0;
	for (i = 1; i < n; i++)
		if (good[i])
			k++;
	printf("%d\n", k);
	return 0;
}

Compilation message

relay.c: In function 'compare':
relay.c:17:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   17 |  int sgn1 = x1 < 0 || x1 == 0 && y1 < 0 ? -1 : 1;
      |                       ~~~~~~~~^~~~~~~~~
relay.c:18:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   18 |  int sgn2 = x2 < 0 || x2 == 0 && y2 < 0 ? -1 : 1;
      |                       ~~~~~~~~^~~~~~~~~
relay.c: In function 'visible':
relay.c:35:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   35 |  return !(l1r1 && r1l2 && l2r2 || r1l2 && l2r2 && r2l1 || l2r2 && r2l1 && l1r1 || r2l1 && l1r1 && r1l2);
      |           ~~~~~~~~~~~~~^~~~~~~
relay.c:35:72: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   35 |  return !(l1r1 && r1l2 && l2r2 || r1l2 && l2r2 && r2l1 || l2r2 && r2l1 && l1r1 || r2l1 && l1r1 && r1l2);
      |                                                           ~~~~~~~~~~~~~^~~~~~~
relay.c:35:96: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   35 |  return !(l1r1 && r1l2 && l2r2 || r1l2 && l2r2 && r2l1 || l2r2 && r2l1 && l1r1 || r2l1 && l1r1 && r1l2);
      |                                                                                   ~~~~~~~~~~~~~^~~~~~~
relay.c: In function 'main':
relay.c:42:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
relay.c:44:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
relay.c:45:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  scanf("%d", &m);
      |  ^~~~~~~~~~~~~~~
relay.c:47:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |   scanf("%d%d", &xx[n + j], &yy[n + j]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

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

Subtask #2
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 3 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 111 ms 476 KB Output is correct
12 Correct 115 ms 476 KB Output is correct
13 Correct 67 ms 448 KB Output is correct
14 Correct 119 ms 452 KB Output is correct
15 Correct 63 ms 440 KB Output is correct
16 Correct 81 ms 460 KB Output is correct
17 Correct 69 ms 576 KB Output is correct
18 Correct 99 ms 460 KB Output is correct
19 Correct 44 ms 448 KB Output is correct
20 Correct 45 ms 452 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 3 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Execution timed out 2060 ms 2792 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 3 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 111 ms 476 KB Output is correct
12 Correct 115 ms 476 KB Output is correct
13 Correct 67 ms 448 KB Output is correct
14 Correct 119 ms 452 KB Output is correct
15 Correct 63 ms 440 KB Output is correct
16 Correct 81 ms 460 KB Output is correct
17 Correct 69 ms 576 KB Output is correct
18 Correct 99 ms 460 KB Output is correct
19 Correct 44 ms 448 KB Output is correct
20 Correct 45 ms 452 KB Output is correct
21 Execution timed out 2060 ms 2792 KB Time limit exceeded
22 Halted 0 ms 0 KB -