Submission #594838

#TimeUsernameProblemLanguageResultExecution timeMemory
594838penguinhackerTriangles (CEOI18_tri)C++17
20 / 100
1 ms324 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...