제출 #1214266

#제출 시각아이디문제언어결과실행 시간메모리
1214266ByeWorldTriangles (CEOI18_tri)C++20
100 / 100
14 ms1800 KiB
#include "trilib.h"
#include <bits/stdc++.h>
// #pragma GCC optimize("O3")
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<int,pii> ipii;
typedef pair<pii,int> piii;
const int MAXN = 1e7+10;
const int SQRT = 450;
const int INF = 1e9+10;
const int MOD = 998244353;
const int LOG = 30;

int n;
vector<int> up, dw, urut;

bool cmp(int a, int b){
	if(is_clockwise(2, a, b)) return 1;
	return 0;
}

vector<int> ANS;
void solve(){
	ANS.clear();
	ANS.pb(urut[0]); ANS.pb(urut[1]);
	for(int i=2; i<urut.size(); i++){
		while(ANS.size()>=2 && !is_clockwise(
			ANS[ANS.size()-2], ANS.back(), urut[i]) ) ANS.pop_back();

		ANS.pb(urut[i]);
	}

	bool done = 0;
	while(!done){
		done = 1;

		int siz = ANS.size();
		for(int i=0; i<ANS.size(); i++){
			if(!is_clockwise( ANS[i], ANS[(i+1)%siz], ANS[(i+2)%siz]) ){
				done = 0;
				vector<int> vec;
				for(int j=0; j<ANS.size(); j++){
					if(j == (i+1)%siz) continue;
					vec.pb(ANS[j]);
				}
				ANS = vec;
				break;
			}
		}
	}

}
signed main(){
	n = get_n();
	if(n==3){ give_answer(n); exit(0); }

	for(int i=3; i<=n; i++){
		if(is_clockwise(1, 2, i)) dw.pb(i);
		else up.pb(i);
	}
	sort(dw.begin(), dw.end(), cmp);
	sort(up.begin(), up.end(), cmp);

	// for(auto in : up) cout << in << " up\n";
	// for(auto in : dw) cout << in << " dw\n";

	urut.pb(1);
	for(auto in : up) urut.pb(in);
	urut.pb(2);
	for(auto in : dw) urut.pb(in);

	solve();

	give_answer((int)ANS.size());
}
#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...