제출 #299622

#제출 시각아이디문제언어결과실행 시간메모리
299622BertedTriangles (CEOI18_tri)C++14
100 / 100
38 ms2424 KiB
#include "trilib.h"
#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>

using namespace std;

int N;
vector<int> data, p1, p2;

bool comp(const int &l, const int &r)
{
	return !is_clockwise(1, l, r);
}

int main()
{
	N = get_n();
	for (int i = 3; i <= N; i++)
	{
		if (is_clockwise(1, i, 2)) {p2.push_back(i);}
		else {p1.push_back(i);}
	}

	sort(p1.begin(), p1.end(), comp);
	for (auto &x : p1) {data.push_back(x);}
	data.push_back(2);
	sort(p2.begin(), p2.end(), comp);
	for (auto &x : p2) {data.push_back(x);}


	//for (auto &x : data) {cout << x << " ";} cout << "\n";

	deque<int> stack;
	stack.push_back(1);
	for (auto &x : data)
	{
		while (stack.size() > 1 && is_clockwise(stack[stack.size() - 2], stack.back(), x)) {stack.pop_back();}
		stack.push_back(x);
		//cout << "inserted " << x << "\n";
	}

	//for (auto &x : stack) {cout << x << " ";} cout << "\n";

	while (stack.size() > 2)
	{
		if (is_clockwise(stack.front(), stack[1], stack.back())) {stack.pop_front();}
		else if (is_clockwise(stack.back(), stack.front(), stack[stack.size() - 2])) {stack.pop_back();}
		else {break;}
	}

	//for (auto &x : stack) {cout << x << " ";} cout << "\n";

	give_answer(stack.size());
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...