Submission #484590

#	Time	Username	Problem	Language	Result	Execution time	Memory
484590		rainboy	Geometrija (COCI21_geometrija)	C11	20 / 110	1092 ms	460 KiB

geometrija

#include <stdio.h>

#define N	1000

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

int intersect(int i, int j, int k, int l) {
	long long cijk = cross(xx[i], yy[i], xx[j], yy[j], xx[k], yy[k]);
	long long cijl = cross(xx[i], yy[i], xx[j], yy[j], xx[l], yy[l]);
	long long ckli = cross(xx[k], yy[k], xx[l], yy[l], xx[i], yy[i]);
	long long cklj = cross(xx[k], yy[k], xx[l], yy[l], xx[j], yy[j]);

	return (cijk > 0) != (cijl > 0) && (ckli > 0) != (cklj > 0);
}

int main() {
	static char bad[N][N];
	int n, i, j, k, l, ans;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	for (i = 0; i < n; i++)
		for (j = i + 1; j < n; j++)
			for (k = j + 1; k < n; k++)
				for (l = k + 1; l < n; l++) {
					if (intersect(i, j, k, l))
						bad[i][j] = bad[k][l] = 1;
					if (intersect(i, k, j, l))
						bad[i][k] = bad[j][l] = 1;
					if (intersect(i, l, j, k))
						bad[i][l] = bad[j][k] = 1;
				}
	ans = 0;
	for (i = 0; i < n; i++)
		for (j = i + 1; j < n; j++)
			if (!bad[i][j])
				ans++;
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

geometrija.c: In function 'main':
geometrija.c:28:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
geometrija.c:30:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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