Submission #825918

#	Time	Username	Problem	Language	Result	Execution time	Memory
825918		sentheta	Triangles (CEOI18_tri)	C++17	100 / 100	20 ms	2444 KiB

tri

// author : sentheta aka vanwij
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
	#define DBG 1
#else
	#include"bits/stdc++.h"
	#define DBG 0
	#include "trilib.h"
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)

#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}

#define int long long
// const Int MOD = 1e9+7;
const Int MOD = 998244353;
Int bpow(Int a,Int b){
	Int ret = 1;
	for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD;
	return ret;
}
Int inv(Int a){return bpow(a,MOD-2);}

void solve(); int TC, ALLTC;
signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed << setprecision(7);
	// cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0;
	solve();
}





#if VANWIJ
int _n;
pii _p[100];
int operator*(pii p,pii q){
	return p.ff*q.ss - p.ss*q.ff;
}
pii operator-(pii p,pii q){
	return {p.ff-q.ff, p.ss-q.ss};
}
void read(){
	cin >> _n;
	rep(i,1,_n+1){
		cin >> _p[i].ff >> _p[i].ss;
	}
}

int get_n(){
	return _n;
}
bool is_clockwise(int i,int j,int k){
	return (_p[j]-_p[i])*(_p[k]-_p[i]) < 0;
}
void give_answer(int x){
	cout << x << nl;
	;
}
#endif





int n;


void solve(){
#if VANWIJ
	read();
#endif
	
	n = get_n();

	// dbg((_p[2]-_p[1]).ff);	
	// dbg((_p[2]-_p[1]).ss);	
	// dbg((_p[5]-_p[1]).ff);	
	// dbg((_p[5]-_p[1]).ss);	
	// dbg((_p[2]-_p[1])*(_p[5]-_p[1]));
	
	V<int> lf, rg;
	for(int i=3; i<=n; i++){
		if(is_clockwise(1,2,i)) rg.push_back(i);
		else lf.push_back(i);
	}
	
	
	sort(all(lf),[&](int i,int j){
		return is_clockwise(1,i,j);
	});
	// 1->...->2
	lf.insert(lf.begin(), 1);
	lf.insert(lf.end(), 2);
	
	sort(all(rg),[&](int i,int j){
		return is_clockwise(1,i,j);
	});
	// 2->...->1
	rg.insert(rg.begin(), 2);
	rg.insert(rg.end(), 1);
	
	cerr << "LEFT" << nl;
	deque<int> lv;
	for(int i : lf){
		dbg(i);
		while(lv.size()>=2 && !is_clockwise(lv.end()[-2],lv.end()[-1],i)) lv.pop_back();
		lv.push_back(i);
	}
	cerr << "HULL" << nl;
	for(int i : lv) dbg(i);
	cerr << nl;
	
	
	cerr << "RIGHT" << nl;
	deque<int> rv;
	for(int i : rg){
		dbg(i);
		while(rv.size()>=2 && !is_clockwise(rv.end()[-2],rv.end()[-1],i)) rv.pop_back();
		rv.push_back(i);
	}
	cerr << "HULL" << nl;
	for(int i : rv) dbg(i);
	cerr << nl;
	
	// empty set create degenerate hull
	// if(lv.size()==2 || rv.size()==2){
	// 	int ans = lv.size() + rv.size() - 2;
	// 	cout << ans << nl;
	// 	return;
	// }
	// lv.pop_front();
	// lv.pop_back();
	rv.pop_front();
	rv.pop_back();
	
	
	// lf->rg
	while(1){
		bool chg = 0;
		
		while(lv.size()>=2 && rv.size()>=1 && !is_clockwise(lv.end()[-2],lv.end()[-1],rv[0])){
			chg = 1;
			lv.pop_back();
		}
		while(lv.size()>=1 && rv.size()>=2 && !is_clockwise(lv.end()[-1],rv[0],rv[1])){
			chg = 1;
			rv.pop_front();
		}
		
		if(!chg) break;
	}
	
	cerr << "FULL" << nl;
	for(int i : lv) dbg(i);
	cerr << "-" << nl;
	for(int i : rv) dbg(i);
	cerr << nl;
	
	// rg->lf
	while(1){
		bool chg = 0;
		
		while(rv.size()>=2 && lv.size()>=1 && !is_clockwise(rv.end()[-2],rv.end()[-1],lv[0])){
			chg = 1;
			rv.pop_back();
		}
		while(rv.size()>=1 && lv.size()>=2 && !is_clockwise(rv.end()[-1],lv[0],lv[1])){
			chg = 1;
			lv.pop_front();
		}
		
		if(!chg) break;
	}
	
	cerr << "FULL" << nl;
	for(int i : lv) dbg(i);
	cerr << "-" << nl;
	for(int i : rv) dbg(i);
	cerr << nl;
	
	
	int ans = lv.size() + rv.size();
	give_answer(ans);
	
	
}

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