제출 #872502

#제출 시각아이디문제언어결과실행 시간메모리
872502lovrotTriangles (CEOI18_tri)C++17
0 / 100
1 ms500 KiB
#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) {
	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;
	});
 
  	vector<int> _V;
  	for(int u : V) { 
		while((int) _V.size() > 1 && ccw(end(_V)[-2], u, end(_V)[-1]) == !s) _V.pop_back(); 
      	_V.EB(u);
	}
  	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;
}
#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...