Submission #485903

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
485903	2021-11-09T16:12:52 Z	rainboy	SIR (COI15_sir)	C	12 / 100	2 ms	332 KB

sir

#include <stdio.h>

#define N	3000
#define M	3000

long long max(long long a, long long b) { return a > b ? a : b; }

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

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

unsigned int X = 12345;

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

int o;

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 = cross(o, 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 jj[M];
	int n, m, cnt, i, i1, i2, j;
	long long ans, area;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[n - 1 - i], &yy[n - 1 - i]);
	scanf("%d", &m);
	for (j = 0; j < m; j++)
		scanf("%d%d", &xx[n + j], &yy[n + j]);
	o = -1;
	for (j = 0; j < m; j++)
		if (o == -1 || xx[o] > xx[n + j] || xx[o] == xx[n + j] && yy[o] > yy[n + j])
			o = n + j;
	for (j = 0; j < m; j++)
		jj[j] = n + j;
	jj[0] = o, jj[o - n] = n + 0;
	sort(jj, 1, m);
	cnt = 0;
	for (j = 0; j < m; j++) {
		while (cnt >= 2 && cross(jj[cnt - 2], jj[cnt - 1], jj[j]) >= 0)
			cnt--;
		jj[cnt++] = jj[j];
	}
	ans = 0, area = 0;
	for (i1 = 0, i2 = 0, j = 0; i1 < n; i1++) {
		while (cross(i1, jj[j], jj[(j + 1) % cnt]) > 0)
			j = (j + 1) % cnt;
		while (cross(i1, jj[j], jj[(j - 1 + cnt) % cnt]) > 0)
			j = (j - 1 + cnt) % cnt;
		while (cross(i1, jj[j], (i2 + 1) % n) > 0) {
			area -= cross2(xx[i2], yy[i2], xx[(i2 + 1) % n], yy[(i2 + 1) % n]);
			i2 = (i2 + 1) % n;
		}
		ans = max(ans, area - cross2(xx[i2], yy[i2], xx[i1], yy[i1]));
		area += cross2(xx[i1], yy[i1], xx[(i1 + 1) % n], yy[(i1 + 1) % n]);
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

sir.c: In function 'main':
sir.c:61:58: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   61 |   if (o == -1 || xx[o] > xx[n + j] || xx[o] == xx[n + j] && yy[o] > yy[n + j])
      |                                       ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
sir.c:53:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
sir.c:55:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d%d", &xx[n - 1 - i], &yy[n - 1 - i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sir.c:56:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  scanf("%d", &m);
      |  ^~~~~~~~~~~~~~~
sir.c:58:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |   scanf("%d%d", &xx[n + j], &yy[n + j]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

12.0 / 12.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	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct

Subtask #2

0 / 39.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	332 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	2 ms	204 KB	Output is correct
6	Incorrect	1 ms	332 KB	Output isn't correct

Subtask #3

0 / 49.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1 ms	332 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-