Submission #545941

#	Time	Username	Problem	Language	Result	Execution time	Memory
545941		rainboy	Roads (CEOI20_roads)	C11	100 / 100	183 ms	10384 KiB

roads

#include <stdio.h>
#include <string.h>

#define N	100000

unsigned int X = 12345;

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

int xx[N * 2], yy[N * 2];

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 = xx[ii[j]] != xx[i_] ? xx[ii[j]] - xx[i_] : yy[ii[j]] - 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 zz[1 + N], ll[1 + N], rr[1 + N], kk[1 + N], u_, l_, r_;

int node(int k) {
	static int _ = 1;

	zz[_] = rand_(), kk[_] = k;
	return _++;
}

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 compare(int i, int j) {
	long long c1, c2;

	if (i == j)
		return 0;
	c1 = cross(xx[i << 1 | 0], yy[i << 1 | 0], xx[i << 1 | 1], yy[i << 1 | 1], xx[j << 1 | 0], yy[j << 1 | 0]);
	c2 = cross(xx[i << 1 | 0], yy[i << 1 | 0], xx[i << 1 | 1], yy[i << 1 | 1], xx[j << 1 | 1], yy[j << 1 | 1]);
	if (c1 != 0 && c2 != 0 && (c1 < 0) == (c2 < 0))
		return c1 < 0 ? -1 : 1;
	c1 = cross(xx[j << 1 | 0], yy[j << 1 | 0], xx[j << 1 | 1], yy[j << 1 | 1], xx[i << 1 | 0], yy[i << 1 | 0]);
	return c1 > 0 ? -1 : 1;
}

void split(int u, int k) {
	int c;

	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	c = compare(kk[u], k);
	if (c < 0) {
		split(rr[u], k);
		rr[u] = l_, l_ = u;
	} else if (c > 0) {
		split(ll[u], k);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v);
		return u;
	} else {
		ll[v] = merge(u, ll[v]);
		return v;
	}
}

int first(int u) { return ll[u] == 0 ? u : first(ll[u]); }
int last(int u) { return rr[u] == 0 ? u : last(rr[u]); }

int main() {
	static int ii[N * 2], rep[N + 1];
	int n, h, i, tmp;

	scanf("%d", &n);
	for (i = 0; i < n * 2; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	for (i = 0; i < n; i++)
		if (xx[i << 1 | 0] > xx[i << 1 | 1] || xx[i << 1 | 0] == xx[i << 1 | 1] && yy[i << 1 | 0] > yy[i << 1 | 1]) {
			tmp = xx[i << 1 | 0], xx[i << 1 | 0] = xx[i << 1 | 1], xx[i << 1 | 1] = tmp;
			tmp = yy[i << 1 | 0], yy[i << 1 | 0] = yy[i << 1 | 1], yy[i << 1 | 1] = tmp;
		}
	for (i = 0; i < n * 2; i++)
		ii[i] = i;
	sort(ii, 0, n * 2);
	memset(rep, -1, (n + 1) * sizeof *rep);
	for (h = 0; h < n * 2; h++) {
		int i_ = ii[h];

		i = i_ >> 1;
		if ((i_ & 1) == 0) {
			int p;

			split(u_, i);
			p = l_ ? kk[last(l_)] : n;
			if (rep[p] != -1) {
				printf("%d %d %d %d\n", xx[rep[p] << 1 | 1], yy[rep[p] << 1 | 1], xx[i_], yy[i_]);
				rep[p] = -1;
			}
			u_ = merge(merge(l_, node(i)), r_);
		} else {
			int p;

			split(u_, i);
			p = l_ ? kk[last(l_)] : n;
			if (rep[p] != -1) {
				printf("%d %d %d %d\n", xx[rep[p] << 1 | 1], yy[rep[p] << 1 | 1], xx[i_], yy[i_]);
				rep[p] = -1;
			}
			if (rep[i] != -1) {
				printf("%d %d %d %d\n", xx[rep[i] << 1 | 1], yy[rep[i] << 1 | 1], xx[i_], yy[i_]);
				rep[i] = -1;
			}
			rep[p] = i;
			u_ = merge(l_, r_);
		}
	}
	return 0;
}

Compilation message (stderr)

roads.c: In function 'main':
roads.c:111:75: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  111 |   if (xx[i << 1 | 0] > xx[i << 1 | 1] || xx[i << 1 | 0] == xx[i << 1 | 1] && yy[i << 1 | 0] > yy[i << 1 | 1]) {
      |                                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
roads.c:107:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
roads.c:109:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 40 / 40