Submission #383514

#	Time	Username	Problem	Language	Result	Execution time	Memory
383514		maximath_1	Triangles (CEOI18_tri)	C++11	20 / 100	2 ms	492 KiB

tri

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

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

	vector<int> v(n - 1, 0);
	iota(v.begin(), v.end(), 2);
	stable_sort(v.begin(), v.end(), [&](int a, int b){
		return is_clockwise(1, a, b);
	});

	// for(int i = 0; i < v.size(); i ++)
	// 	cout << v[i] << " ";
	// cout << endl;

	int id = -1;
	for(int j = 1; j < v.size(); j ++){
		if(!is_clockwise(v[0], v[j], 1)){
			id = j;
			break;
		}
	}
	if(id == -1) {v.push_back(1); id = v.size();}
	else if(id == 1){
		v.insert(v.begin() + 1, 1);
		id = v.size();
	}

	vector<int> ch1, ch2;
	
	for(int i = 0; i < id; i ++){
		while(ch1.size() >= 2 && !is_clockwise(ch1[ch1.size() - 2], ch1.back(), v[i])) ch1.pop_back();
		ch1.push_back(v[i]);

		// cout << "insert " << v[i] << " in ch1\n";
		// for(int j : ch1)
		// 	cout << j << " ";
		// cout << endl;
	}

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

		// cout << "insert " << v[i] << " in ch2\n";
		// for(int j : ch2)
		// 	cout << j << " ";
		// cout << endl;
	}

	give_answer(ch1.size() + ch2.size());
}

int main(){
	getConvexHull();
}

Compilation message (stderr)

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

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