Submission #459274

#	Time	Username	Problem	Language	Result	Execution time	Memory
459274		hhhhaura	Triangles (CEOI18_tri)	C++14	100 / 100	43 ms	1500 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define all(x) x.begin(), x.end()
using namespace std;
vector<int> v[2], hull;
void solve() {
	int n = get_n();
	v[0].push_back(1);
	v[1].push_back(2);
	rep(i, 3, n) v[is_clockwise(2, 1, i)].push_back(i);
	rep(i, 0, 1) sort(v[i].begin() + 1, v[i].end(), 
		[](int a, int b) { return is_clockwise(1, b, a);});
	rep(tp, 0, 1) {
		for(auto i : v[tp]) {
			while(hull.size() > 1 && is_clockwise(
				hull[hull.size() - 1], i, hull[hull.size() - 2])) hull.pop_back(); 
			hull.push_back(i);
		}
	}
	int ft = 0, bk = hull.size() - 1;
	while(true) {
		bool done = 1;
		while(is_clockwise(hull[bk], hull[ft], hull[bk - 1])) {
			done = 0, bk--;
		}
		while(is_clockwise(hull[ft], hull[ft + 1], hull[bk])) {
			done = 0, ft++;
		}
		if(done) break;
	}
	give_answer(bk - ft + 1);
	return;
}
signed main() {
	solve();
	return 0;
}

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