Submission #484596

#	Time	Username	Problem	Language	Result	Execution time	Memory
484596		rainboy	Geometrija (COCI21_geometrija)	C11	110 / 110	639 ms	344 KiB

geometrija

#include <stdio.h>

#define N	1000

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], yy[N], n, o;

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

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 intersect(int i, int j, int k, int l) {
	return (cross(i, j, k) > 0) != (cross(i, j, l) > 0) && (cross(k, l, i) > 0) != (cross(k, l, j) > 0);
}

int good(int i, int j) {
	static int kk[N], ll[N];
	int nk, nl, k, l, l_;

	nk = 0, nl = 0;
	for (k = 0; k < n; k++)
		if (k != i && k != j) {
			if (cross(i, j, k) > 0)
				kk[nk++] = k;
			else
				ll[nl++] = k;
		}
	o = i, sort(kk, 0, nk), sort(ll, 0, nl);
	for (k = 0, l = 0, l_ = -1; k < nk; k++) {
		while (l < nl && cross(i, kk[k], ll[l]) < 0) {
			if (l_ == -1 || cross(j, l_, ll[l]) < 0)
				l_ = ll[l];
			l++;
		}
		if (l_ != -1 && cross(j, l_, kk[k]) < 0)
			return 0;
	}
	return 1;
}

int main() {
	static int ii[N], uu[N * 3], vv[N * 3], ww[N * 3];
	static char hull[N];
	int m, h, i, cnt;

	scanf("%d", &n);
	o = -1;
	for (i = 0; i < n; i++) {
		scanf("%d%d", &xx[i], &yy[i]);
		if (o == -1 || xx[o] > xx[i] || xx[o] == xx[i] && yy[o] > yy[i])
			o = i;
		ii[i] = i;
	}
	ii[0] = o, ii[o] = 0;
	sort(ii, 1, n);
	m = 0;
	for (i = 0; i < n; i++) {
		while (m >= 2 && cross(ii[m - 2], ii[m - 1], ii[i]) >= 0)
			m--;
		ii[m++] = ii[i];
	}
	cnt = m;
	for (h = 0; h < m; h++)
		hull[ii[h]] = 1;
	for (h = 0; h + 2 < m; h++)
		uu[h] = ii[0], vv[h] = ii[h + 1], ww[h] = ii[h + 2];
	m -= 2;
	for (i = 0; i < n; i++)
		if (!hull[i]) {
			for (h = 0; h < m; h++) {
				int u = uu[h], v = vv[h], w = ww[h];

				if (cross(i, u, v) < 0 && cross(i, v, w) < 0 && cross(i, w, u) < 0) {
					while (h + 1 < m)
						uu[h] = uu[h + 1], vv[h] = vv[h + 1], ww[h] = ww[h + 1], h++;
					m--;
					uu[m] = i, vv[m] = u, ww[m] = v, m++;
					uu[m] = i, vv[m] = v, ww[m] = w, m++;
					uu[m] = i, vv[m] = w, ww[m] = u, m++;
				}
			}
		}
	for (h = 0; h < m; h++) {
		int u = uu[h], v = vv[h], w = ww[h];

		if (good(u, v))
			cnt++;
		if (good(v, w))
			cnt++;
		if (good(w, u))
			cnt++;
	}
	cnt /= 2;
	printf("%d\n", cnt);
	return 0;
}

Compilation message (stderr)

geometrija.c: In function 'main':
geometrija.c:81:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   81 |   if (o == -1 || xx[o] > xx[i] || xx[o] == xx[i] && yy[o] > yy[i])
      |                                   ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
geometrija.c:77:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
geometrija.c:80:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60