Submission #1166278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166278		sleepntsheep	Triangles (CEOI18_tri)	C11	0 / 100	0 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;
	}

	top = 0;
	for (int i = 2; i <= chb; ++i)
		sta[++top] = ch_low[i];
	
	for (int i = 2; i <= cha; ++i)
		sta[++top] = ch_high[i];


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

	while (top2 >= 2 && is_clockwise(sta2[top2 - 1], sta2[top2], sta2[1]))
		--top2;

	give_answer(top2);
	return 0;
}

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