제출 #1143094

#제출 시각아이디문제언어결과실행 시간메모리
1143094fabijan_cikacTriangles (CEOI18_tri)C++20
100 / 100
20 ms3596 KiB
#include <bits/stdc++.h>
#include "trilib.h"

using namespace std;

#define pb push_back

/*int get_n(){
	int n; cin >> n; return n;
}*/

/*bool is_clockwise(int x, int y, int z){
	cout << "?? " << x << ' ' << y << ' ' << z << endl;
	bool b; cin >> b; return b;
}*/

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

/*void give_answer(int x){
	cout << x << endl;
}*/

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);
	}
	
	/*for (int x: v[0])
		cout << x << ' ';
	cout << endl;
	for (int x: v[1])
		cout << x << ' ';
	cout << endl;*/
		
	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);
	}
	
	/*for (int x: c[0])
		cout << x << ' ';
	cout << endl;
	for (int x: c[1])
		cout << x << ' ';
	cout << endl;*/
	
	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...