Submission #73785

#	Time	Username	Problem	Language	Result	Execution time	Memory
73785		jiaqing23	Triangles (CEOI18_tri)	C++14	0 / 100	4 ms	616 KiB

tri

// Mateusz Radecki
// Queries: O(n*log(n))
// Complexity: O(n*log(n))

//Testing
 
#include <bits/stdc++.h>
#include "trilib.h"
using namespace std;
 
int n;
vector <int> divide[2], hull[2];
 
bool is_less(int a, int b)
{
	return is_clockwise(1, a, b);
}
 
int main()
{
	n=get_n();
	divide[0]=divide[1]={2};
	for (int i=3; i<=n; i++)
		divide[is_clockwise(1, 2, i)].push_back(i);
	for (int h=0; h<2; h++)
	{
		sort(divide[h].begin(), divide[h].end(), is_less);
		for (int i : divide[h])
		{
			int r=hull[h].size();
			while (r>1 && !is_clockwise(hull[h][r-2], hull[h][r-1], i))
			{
				r--;
				hull[h].pop_back();
			}
			hull[h].push_back(i);
		}
		
		if (h)
			reverse(hull[h].begin(), hull[h].end());
		hull[h].insert(hull[h].begin(), 1);
	}
	if ((int)min(hull[0].size(), hull[1].size())==2)
	{
		give_answer(max(hull[0].size(), hull[1].size()));
		return 0;
	}

	give_answer(hull[0].size()+hull[1].size()-2);
	return 0;
}

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