Submission #266581

#	Time	Username	Problem	Language	Result	Execution time	Memory
266581		islingr	Triangles (CEOI18_tri)	C++17	100 / 100	34 ms	2680 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
using namespace std;

#define rep(i, a, b) for (auto i = (a); i <= (b); ++i)
#define all(x...) begin(x), end(x)

const int N = 1 << 17;
bool halfplane[N];

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n = get_n();
	vector<int> upper, lower;
	halfplane[1] = 0;
	rep(i, 3, n) {
		halfplane[i] = is_clockwise(1, 2, i);
		(halfplane[i] ? lower : upper).push_back(i);
	}
	sort(all(upper), [](int x, int y) -> bool {
		if (x == y) return false;
		return !is_clockwise(2, x, y);
	});
	vector<int> upper_hull = {2}; int t = 1;
	for (int i : upper) {
		while (t > 1 && is_clockwise(upper_hull[t - 2], upper_hull[t - 1], i)) upper_hull.pop_back(), --t;
		upper_hull.push_back(i); ++t;
	}

	sort(all(lower), [](int x, int y) -> bool {
		if (x == y) return false;
		return !is_clockwise(1, x, y);
	});

	vector<int> lower_hull = {1}; t = 1;
	for (int i : lower) {
		while (t > 1 && is_clockwise(lower_hull[t - 2], lower_hull[t - 1], i)) lower_hull.pop_back(), --t;
		lower_hull.push_back(i); ++t;
	}

	vector<int> hull = upper_hull; t = hull.size();
	for (int i : lower_hull) {
		while (t > 1 && is_clockwise(hull[t - 2], hull[t - 1], i)) hull.pop_back(), --t;
		hull.push_back(i); ++t;
	}

	auto it = begin(hull);
	while (it != end(hull) && !halfplane[*it]) ++it;
	
	upper_hull = {begin(hull), it};
	hull.erase(begin(hull), it);
	t = hull.size();
	for (int i : upper_hull) {
		if (t > 1 && halfplane[hull[t - 2]])
			while (t > 1 && is_clockwise(hull[t - 2], hull[t - 1], i)) hull.pop_back(), --t;
		hull.push_back(i); ++t;
	}

	give_answer(hull.size());
}

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