Submission #128418

#	Time	Username	Problem	Language	Result	Execution time	Memory
128418		TadijaSebez	Triangles (CEOI18_tri)	C++11	75 / 100	31 ms	1784 KiB

tri

#include "trilib.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
vector<int> Hull(vector<int> v)
{
	sort(v.begin(),v.end(),[](int x, int y){ return is_clockwise(1,y,x);});
	vector<int> ans;
	ans.pb(1);
	for(int i:v)
	{
		while(ans.size()>1 && is_clockwise(ans[ans.size()-2],ans.back(),i)) ans.pop_back();
		ans.pb(i);
	}
	return ans;
}
const int N=40050;
bool in[N];
int nxt[N],pre[N];
vector<int> Merge(vector<int> x, vector<int> y)
{
	swap(x,y);
	reverse(y.begin()+1,y.end());
	for(int t=0;t<2;t++)
	{
		x.pop_back();
		while(1)
		{
			bool ok=0;
			int sz=x.size();
			if(sz>1 && is_clockwise(x[sz-2],x[sz-1],y.back())) x.pop_back(),ok=1;
			sz=y.size();
			if(sz>1 && is_clockwise(x.back(),y[sz-1],y[sz-2])) y.pop_back(),ok=1;
			if(!ok) break;
		}
		reverse(x.begin(),x.end());
		reverse(y.begin(),y.end());
		swap(x,y);
	}
	vector<int> ans;
	for(int i:x) ans.pb(i);
	for(int i:y) ans.pb(i);
	return ans;
}
int main()
{
	int n=get_n();
	vector<int> v[2];
	for(int i=3;i<=n;i++) v[is_clockwise(1,2,i)].pb(i);
	if(v[0].empty() || v[1].empty())
	{
		if(v[0].empty()) v[0]=v[1];
		v[0].pb(2);
		v[0]=Hull(v[0]);
		give_answer(v[0].size());
		return 0;
	}
	v[0].pb(2);
	v[1].pb(2);
	v[0]=Hull(v[0]);
	v[1]=Hull(v[1]);
	vector<int> all=Merge(v[0],v[1]);
	give_answer(all.size());
	return 0;
}

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