Submission #1166289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166289		sleepntsheep	Triangles (CEOI18_tri)	C11	0 / 100	1 ms	840 KiB

tri

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

int sta[55555], top, n, low[55555], q, w, a[55555], b[55555], c, d, ch_high[55555], ch_low[55555], cha, chb
		, sta2[55555], top2;

int cmp_high(const void *ii, const void *jj) {
	return ! is_clockwise(q, *(int*)ii, *(int*)jj);
}

int cmp_low(const void *ii, const void *jj) {
	return ! is_clockwise(q, *(int*)ii, *(int*)jj);
}



int main() {
	n = get_n();

	q = 1;
	w = 2;

	for (int i = 3; i <= n; ++i) {
		if (is_clockwise(q, w, i)) {
			low[i] = 1;
			a[c++] = i;
		} else {
			low[i] = 0;
			b[d++] = i;
		}
	}

	qsort(b, d, sizeof *b, cmp_high);
	qsort(a, c, sizeof *a, cmp_low);

	sta[top = 1] = w;

	for (int i = 0; i < d; ++i) {
		int j = b[i];
		while (top >= 2 && is_clockwise(sta[top - 1], sta[top], j))
			--top;
		sta[++top] = j;
	}
	while (top >= 2 && is_clockwise(sta[top - 1], sta[top], q))
		--top;
	sta[++top] = q;

	cha = top;
	memcpy(ch_high, sta, sizeof sta);

	sta[top = 1] = q;
	for (int i = 0; i < c; ++i) {
		int j = a[i];
		while (top >= 2 && is_clockwise(sta[top - 1], sta[top], j))
			--top;
		sta[++top] = j;
	}
	while (top >= 2 && is_clockwise(sta[top - 1], sta[top], w))
		--top;
	sta[++top] = w;

	chb = top;
	memcpy(ch_low, sta, sizeof sta);

	if (cha == 2) {
		give_answer(chb);
		return 0;
	}
	if (chb == 2) {
		give_answer(cha);
		return 0;
	}

	/* stitch around q */

	--cha;
	--chb;
	int sta = 0, stb = 0;
	while (cha - sta > 1 && chb - stb > 1) {
		int f = 0;
		while (chb - stb > 2) {
			if (is_clockwise(ch_high[cha - 1], ch_low[stb + 1], ch_low[stb + 2])) {
				++stb;
				++f;
			}
			else break;
		}

		while (cha - sta > 2) {
			if (is_clockwise(ch_low[chb - 1], ch_low[sta + 1], ch_low[sta + 2])) {
				++sta;
				++f;
			}
			else break;
		}

		if (! f)
			break;
	}



	give_answer(cha + chb - sta - stb);
	return 0;
}

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