Submission #169871

#	Time	Username	Problem	Language	Result	Execution time	Memory
169871		arnold518	Triangles (CEOI18_tri)	C++14	55 / 100	3052 ms	205596 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll MAXN = 40001;

int N, p, q;
vector<int> A, B;
list<int> C;

list<int>::iterator bef(list<int>::iterator t)
{
	if(t!=C.begin()) return prev(t);
	else return prev(C.end());
}

list<int>::iterator nxt(list<int>::iterator t)
{
	if(t==prev(C.end())) return C.begin();
	else return next(t);
}

int cnt=0;
unordered_map<ll, bool> M;

ll f(int a, int b, int c) { return MAXN*(MAXN*a+b)+c; }

bool ccw(int a, int b, int c)
{
	if(M.find(f(a, b, c))!=M.end()) return M[f(a, b, c)];
	if(M.find(f(b, c, a))!=M.end()) return M[f(b, c, a)];
	if(M.find(f(c, a, b))!=M.end()) return M[f(c, a, b)];
	if(M.find(f(c, b, a))!=M.end()) return !M[f(c, b, a)];
	if(M.find(f(a, c, b))!=M.end()) return !M[f(a, c, b)];
	if(M.find(f(b, a, c))!=M.end()) return !M[f(b, a, c)];
	cnt++;
	if(cnt>=999999) assert(1);
	bool t=is_clockwise(a, b, c);
	M[f(a, b, c)]=M[f(b, c, a)]=M[f(c, a, b)]=!t;
	M[f(c, b, a)]=M[f(a, c, b)]=M[f(b, a, c)]=t;
	return !t;
}

int main()
{
	int i, j;
	N=get_n();

	for(i=3; i<=N; i++)
	{
		if(ccw(1, 2, i)) A.push_back(i);
		else B.push_back(i);
	}

	A.push_back(2); B.push_back(2);
	sort(A.begin(), A.end(), [&](const int &p, const int &q) { return ccw(1, p, q); });
	sort(B.begin(), B.end(), [&](const int &p, const int &q) { return !ccw(1, p, q); });

	A.insert(A.begin(), 1);
	B.insert(B.begin(), 1);

	vector<int> S;
	for(auto it : A)
	{
		while(S.size()>1 && !ccw(S[S.size()-2], S[S.size()-1], it)) S.pop_back();
		S.push_back(it);
	}
	A=S; S.clear();

	for(auto it : B)
	{
		while(S.size()>1 && ccw(S[S.size()-2], S[S.size()-1], it)) S.pop_back();
		S.push_back(it);
	}
	B=S; S.clear();	

	A.erase(A.begin()); A.erase(A.begin());
	B.erase(B.begin()); B.erase(B.begin()); 
	reverse(B.begin(), B.end());

	queue<list<int>::iterator> Q;
	C.push_back(1);
	for(auto it : B) C.push_back(it);
	C.push_back(2);
	for(auto it : A) C.push_back(it);

	set<int> vis;
	for(auto it=C.begin(); it!=C.end(); it++) if(!ccw(*bef(it), *it, *nxt(it))) Q.push(it), vis.insert(*it);

	while(!Q.empty() && C.size()>3)
	{
		auto now=Q.front(); Q.pop();
		
		auto l=bef(now), r=nxt(now);
		C.erase(now);

		if(vis.find(*l)==vis.end() && !ccw(*bef(l), *l, *nxt(l))) Q.push(l), vis.insert(*l);
		if(vis.find(*r)==vis.end() && !ccw(*bef(r), *r, *nxt(r))) Q.push(r), vis.insert(*r);
	}
	give_answer(C.size());
}

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:50:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^

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