Submission #485916

#	Time	Username	Problem	Language	Result	Execution time	Memory
485916		rainboy	SIR (COI15_sir)	C11	100 / 100	213 ms	5392 KiB

sir

#include <stdio.h>

#define N	300000
#define M	300000

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;

int compare(int i, int j) {
	long long c = cross(o, i, j);

	if (c != 0)
		return c < 0 ? -1 : 1;
	if (xx[i] != xx[j])
		return xx[i] < xx[j] ? -1 : 1;
	if (yy[i] != yy[j])
		return yy[i] < yy[j] ? -1 : 1;
	return 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) {
			int 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 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 (stderr)

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

• Subtask 1: 12 / 12
• Subtask 2: 39 / 39
• Subtask 3: 49 / 49