Submission #70767

#	Time	Username	Problem	Language	Result	Execution time	Memory
70767		Diuven	Triangles (CEOI18_tri)	C++14	100 / 100	1041 ms	56124 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
using namespace std;
typedef pair<int, int> pii;
const int MX=40010;


int n;

map<pii, bool> mem[MX];

bool ccw(int a, int b, int c){
	if(mem[a].find({b,c})!=mem[a].end()) return mem[a][pii(b,c)];
	if(mem[a].find({c,b})!=mem[a].end()) return !mem[a][pii(c,b)];
	return mem[a][pii(b,c)]=is_clockwise(a,b,c);
}

vector<int> L, R;

vector<int> get_hull(int s, vector<int> V){
	sort(V.begin(), V.end(), [=](int a, int b){ return ccw(s,a,b); });
	vector<int> R;
	R.push_back(s);
	for(int v:V){
		while(R.size()>=2U && !ccw(R[R.size()-2], R[R.size()-1], v)) R.pop_back();
		R.push_back(v);
	}
	return R;
}

vector<int> all_hull(int v){
	vector<int> V;
	for(int i=1; i<=n; i++) if(i!=v) V.push_back(i);
	return get_hull(v, V);
}

int solve(){

	for(int i=3; i<=n; i++){
		if(ccw(1,2,i)) R.push_back(i);
		else L.push_back(i);
	}

	if(L.empty() || R.empty()) return all_hull(1).size();
	if(L.size()==1U) return all_hull(L[0]).size();
	if(R.size()==1U) return all_hull(R[0]).size();

	vector<int> LH, RH;
	LH=get_hull(1, L), RH=get_hull(2, R);

	int u=-1, v=-1, p=-1, q=-1;

	// upper tangent
	for(int p1=0, p2=0, lsz=LH.size(), rsz=RH.size(); p1<lsz; p1++){
		while(true){
			int a=(p2+rsz-1)%rsz, b=(p2+1)%rsz;
			if(!ccw(LH[p1], RH[p2], RH[a])){ p2=a; continue; }
			if(!ccw(LH[p1], RH[p2], RH[b])){ p2=b; continue; }
			break;
		}
		int a=(p1+lsz-1)%lsz, b=(p1+1)%lsz;
		if(ccw(RH[p2], LH[p1], LH[a])) continue;
		if(ccw(RH[p2], LH[p1], LH[b])) continue;
		assert(u<0 && v<0);
		u=p1, v=p2;
		break;
	}

	// lower tangent
	for(int p1=0, p2=0, lsz=LH.size(), rsz=RH.size(); p1<lsz; p1++){
		while(true){
			int a=(p2+rsz-1)%rsz, b=(p2+1)%rsz;
			if(ccw(LH[p1], RH[p2], RH[a])){ p2=a; continue; }
			if(ccw(LH[p1], RH[p2], RH[b])){ p2=b; continue; }
			break;
		}
		int a=(p1+lsz-1)%lsz, b=(p1+1)%lsz;
		if(!ccw(RH[p2], LH[p1], LH[a])) continue;
		if(!ccw(RH[p2], LH[p1], LH[b])) continue;
		assert(p<0 && q<0);
		p=p1, q=p2;
		break;
	}

	int cnt=0, pos;
	
	pos=v;
	while(true){
		cnt++;
		if(pos==q) break;
		pos=(pos+1)%RH.size();
	}
	pos=p;
	while(true){
		cnt++;
		if(pos==u) break;
		pos=(pos+1)%LH.size();
	}

	return cnt;
}

int main(){
	n=get_n();
	give_answer(solve());
	return 0;
}

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