Submission #594838

#	Time	Username	Problem	Language	Result	Execution time	Memory
594838		penguinhacker	Triangles (CEOI18_tri)	C++17	20 / 100	1 ms	324 KiB

tri

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

#define ll long long
#define ar array

// solution idea: find any point on the hull. a point is on the hull if it isn't contained inside any triangle, so we can maintain this triangle
// after this just use graham scan: sort by angle and then sweep

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n=get_n();
	int a=1, b=2, c=3;
	for (int i=4; i<=n; ++i) {
		bool s1=is_clockwise(a, b, i), s2=is_clockwise(b, c, i), s3=is_clockwise(c, a, i), s4=is_clockwise(a, b, c);
		for (int rep=0; rep<3; ++rep) {
			if (s1==s3&&s1!=s4) {
				a=i;
				break;
			}
			swap(s1, s2);
			swap(s2, s3);
			swap(a, b);
			swap(b, c);
		}
	}
	int fix=a;
	vector<int> points;
	for (int i=1; i<=n; ++i)
		if (i!=fix)
			points.push_back(i);
	sort(points.begin(), points.end(), [&](int i, int j) { return is_clockwise(fix, j, i); });
	vector<int> hull={fix};
	for (int i : points) {
		while(hull.size()>=2&&is_clockwise(hull.end()[-2], hull.back(), i))
			hull.pop_back();
		hull.push_back(i);
	}
	give_answer(hull.size());
	return 0;
}

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