Submission #684195

#	Time	Username	Problem	Language	Result	Execution time	Memory
684195		rainboy	Dragon 2 (JOI17_dragon2)	C11	100 / 100	3756 ms	3968 KiB

dragon2

#include <stdio.h>
#include <stdlib.h>

#define N	30000

long long cross(int x1, int y1, int x2, int y2) {
	return (long long) x1 * y2 - (long long) x2 * y1;
}

int inside(int x1, int y1, int x2, int y2, int x3, int y3) {
	int tmp;

	if (cross(x1, y1, x2, y2) > 0)
		tmp = x1, x1 = x2, x2 = tmp, tmp = y1, y1 = y2, y2 = tmp;
	return cross(x1, y1, x3, y3) < 0 && cross(x3, y3, x2, y2) < 0;
}

int *ei[N], eo[N];

void append(int c, int i) {
	int o = eo[c]++;

	if (o >= 2 && (o & o - 1) == 0)
		ei[c] = (int *) realloc(ei[c], o * 2 * sizeof *ei[c]);
	ei[c][o] = i;
}

int main() {
	static int xx[N], yy[N];
	int n, m, q, i, j, c, x1, y1, x2, y2;

	scanf("%d%d", &n, &m);
	for (c = 0; c < m; c++)
		ei[c] = (int *) malloc(2 * sizeof *ei[c]);
	for (i = 0; i < n; i++) {
		scanf("%d%d%d", &xx[i], &yy[i], &c), c--;
		append(c, i);
	}
	scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &q);
	while (q--) {
		int a, b, ans, o, o_;

		scanf("%d%d", &a, &b), a--, b--;
		ans = 0;
		for (o = eo[a]; o--; ) {
			i = ei[a][o];
			for (o_ = eo[b]; o_--; ) {
				j = ei[b][o_];
				if (inside(x1 - xx[i], y1 - yy[i], x2 - xx[i], y2 - yy[i], xx[j] - xx[i], yy[j] - yy[i]))
					ans++;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

Compilation message (stderr)

dragon2.c: In function 'append':
dragon2.c:23:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   23 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
dragon2.c: In function 'main':
dragon2.c:32:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
dragon2.c:36:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |   scanf("%d%d%d", &xx[i], &yy[i], &c), c--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.c:39:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.c:43:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%d%d", &a, &b), a--, b--;
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40