Submission #545925

#	Time	Username	Problem	Language	Result	Execution time	Memory
545925		rainboy	Triangles (CEOI18_tri)	C11	100 / 100	35 ms	2204 KiB

tri

#include "trilib.h"
#include <string.h>

#define N	40000

int side[N];

void sort(int *ii, int n) {
	static int jj[N];
	int m, i, j, k;

	if (n == 1)
		return;
	m = n / 2;
	sort(ii, m), sort(ii + m, n - m);
	i = 0, j = m, k = 0;
	while (i < m && j < n)
		jj[k++] = side[ii[i]] < side[ii[j]] || side[ii[i]] == side[ii[j]] && is_clockwise(1, ii[i] + 1, ii[j] + 1) ? ii[i++] : ii[j++];
	while (i < m)
		jj[k++] = ii[i++];
	while (j < n)
		jj[k++] = ii[j++];
	memcpy(ii, jj, n * sizeof *jj);
}

int main() {
	static int ii[N];
	int n, i, head, cnt;

	n = get_n();
	for (i = 0; i < n; i++)
		ii[i] = i;
	for (i = 1; i < n; i++)
		side[i] = i == 1 || is_clockwise(1, 2, i + 1) ? 1 : -1;
	sort(ii + 1, n - 1);
	cnt = 0;
	for (i = 0; i < n; i++) {
		while (cnt >= 2 && !is_clockwise(ii[cnt - 2] + 1, ii[cnt - 1] + 1, ii[i] + 1))
			cnt--;
		ii[cnt++] = ii[i];
	}
	head = 0;
	while (cnt > 3)
		if (!is_clockwise(ii[head + cnt - 2] + 1, ii[head + cnt - 1] + 1, ii[head] + 1))
			cnt--;
		else if (!is_clockwise(ii[head + cnt - 1] + 1, ii[head] + 1, ii[head + 1] + 1))
			head++, cnt--;
		else
			break;
	give_answer(cnt);
	return 0;
}

Compilation message (stderr)

tri.c: In function 'sort':
tri.c:18:69: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   18 |   jj[k++] = side[ii[i]] < side[ii[j]] || side[ii[i]] == side[ii[j]] && is_clockwise(1, ii[i] + 1, ii[j] + 1) ? ii[i++] : ii[j++];
      |                                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25