Submission #1143095

#TimeUsernameProblemLanguageResultExecution timeMemory
1143095fabijan_cikacTriangles (CEOI18_tri)C++20
100 / 100
20 ms3144 KiB
#include <bits/stdc++.h>
#include "trilib.h"

using namespace std;

#define pb push_back

bool ccw(int x, int y, int z){
	return is_clockwise(x, y, z);
}

int n, a, b;

bool cmp(int x, int y){
	if (x == y) return 0;
	return !ccw(a, x, y);
}

int main(){
	n = get_n();
	a = n - 1, b = n;
	
	vector<int> v[2];
	for (int i = 1; i <= n - 2; ++i)
		v[!ccw(a, b, i)].pb(i);
	for (int i = 0; i < 2; ++i){
		sort(v[i].begin(), v[i].end(), cmp);
		v[i].pb(b), swap(a, b);
	}
		
	vector<int> c[2];
	for (int i = 0; i < 2; ++i){
		c[i].pb(a);
		for (int x: v[i]){
			while ((int)(c[i].size()) >= 2 && ccw(c[i][(int)(c[i].size()) - 2], c[i].back(), x))
				c[i].pop_back();
			c[i].pb(x);
		}
		swap(a, b);
	}
	
	if ((int)(c[0].size()) == 2 || (int)(c[1].size()) == 2){
		give_answer((int)(c[0].size()) + (int)(c[1].size()) - 2); return 0;
	}
	
	int l1 = 0, r1 = (int)(c[1].size()) - 2;
	int l2 = (int)(c[0].size()) - 2, r2 = 0;
	
	while (1){
		if (ccw(c[1][r1], c[0][l1], c[0][l1 + 1])) ++l1;
		else if (ccw(c[1][r1 - 1], c[1][r1], c[0][l1])) --r1;
		else break;
	}
	
	while (1){
		if (ccw(c[0][l2], c[1][r2], c[1][r2 + 1])) ++r2;
		else if (ccw(c[0][l2 - 1], c[0][l2], c[1][r2])) --l2;
		else break;
	}
	
	set<int> s;
	for (int i = l1; i <= l2; ++i)
		s.insert(c[0][i]);
	for (int i = r2; i <= r1; ++i)
		s.insert(c[1][i]);

	give_answer((int)(s.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...