Submission #872727

#	Time	Username	Problem	Language	Result	Execution time	Memory
872727		lovrot	Triangles (CEOI18_tri)	C++17	100 / 100	15 ms	2344 KiB

tri

#include <cstdio> 
#include <vector> 
#include <stack> 
#include <vector>
#include "trilib.h"
#include <algorithm> 

#define EB emplace_back

using namespace std;

const int N = 4e4 + 10; 

vector<int> S[2]; 

bool ccw(int a, int b, int c) {
	return is_clockwise(a, b, c);
}

void output(vector<int> V) {
//	sort(V.begin(), V.end());
	for(int x : V) printf("%d ", x);
	printf("\n");
}

void half(vector<int> &V, bool s) {
	sort(V.begin(), V.end(), [s](int a, int b) {
		return ccw(1, a, b) == !s;
	});
	
	if(!s) V.insert(V.begin(), 1);
	else V.EB(2);

	vector<int> _V; 
	for(int x : V) {
		while((int) _V.size() > 1 && ccw(x, end(_V)[-2], end(_V)[-1]) == s) _V.pop_back(); 
		_V.EB(x);
	}
	V = _V;
}

void cut() {	
	int fail = 0;
	bool s = 0;
	while(!S[0].empty() && !S[1].empty() && fail < 2) {
		s ^= 1;
		if((int) S[s].size() < 2 || ccw(S[!s].back(), end(S[s])[-2], end(S[s])[-1]) == !s) {	
			++fail;
		} else {
//			printf("%d %d %d : %d\n", S[!s].back(), end(S[s])[-2], end(S[s])[-1], ccw(S[!s].back(), end(S[s])[-2], end(S[s])[-1]));
			fail = 0;
			S[s].pop_back();
		}
	}
}

int main() {
	int n = get_n(); 

	for(int i = 3; i <= n; ++i) S[ccw(1, 2, i)].EB(i); 
	
	half(S[0], 0);
	half(S[1], 1);
	
//	S[0].insert(S[0].begin(), 1); 
//	S[1].EB(2); 
	
//	output(S[0]);
//	output(S[1]);

	cut();

	reverse(S[0].begin(), S[0].end()); 
	reverse(S[1].begin(), S[1].end()); 
	swap(S[0], S[1]);

	cut(); 

	printf("%d\n", (int) S[0].size() + (int) S[1].size()); 
	return 0;
}

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