Submission #383531

#	Time	Username	Problem	Language	Result	Execution time	Memory
383531		maximath_1	Triangles (CEOI18_tri)	C++11	100 / 100	28 ms	2156 KiB

tri

#include "trilib.h"
#include <iostream>
#include <assert.h>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <deque>
using namespace std;

void getConvexHull(){
	int n = get_n();

	vector<int> v[2];
	deque<int> ch;

	v[0].push_back(1); v[0].push_back(2);
	for(int i = 3; i <= n; i ++)
		v[is_clockwise(1, 2, i)].push_back(i);

	for(int tp = 0; tp < 2; tp ++){
		sort(v[tp].begin() + (tp == 0), v[tp].end(), [&](int a, int b){
			return is_clockwise(1, a, b);
		});

		for(int i = 0; i < v[tp].size(); i ++){
			while(ch.size() >= 2 && !is_clockwise(ch[ch.size() - 2], ch.back(), v[tp][i]))
				ch.pop_back();
			ch.push_back(v[tp][i]);
		}
	}

	for(bool done = 0; !done;){
		done = 1;
		if(ch.size() >= 2 && !is_clockwise(ch[ch.size() - 2], ch.back(), ch.front())){
			ch.pop_back(); done = 0;
			continue;
		}
		if(ch.size() >= 2 && !is_clockwise(ch.back(), ch[0], ch[1])){
			ch.pop_front(); done = 0;
			continue;
		}
	}

	give_answer(ch.size());
}

int main(){
	getConvexHull();
}

Compilation message (stderr)

tri.cpp: In function 'void getConvexHull()':
tri.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for(int i = 0; i < v[tp].size(); i ++){
      |                  ~~^~~~~~~~~~~~~~

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