Submission #267126

#	Time	Username	Problem	Language	Result	Execution time	Memory
267126		bigg	Triangles (CEOI18_tri)	C++14	100 / 100	37 ms	2304 KiB

tri

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

int getn(){
	int n;
	//scanf("%d", &n);
	n = get_n();
	return n;
}

bool isclokwise(int x, int y, int z){
	int ok;
	//printf("%d %d %d\n",x, y, z ),	scanf("%d", &ok);;
	ok = is_clockwise(x, y, z);
	return ok;
}

void giveans(int x){
	//printf("%d\n",x );
	give_answer(x);
}
bool comp(int x, int y){
	return isclokwise(1, x, y);
}
vector<int> qualmetade[5], hull[5];

int n;
int main(){

	n = getn();
	qualmetade[0].push_back(2);
	qualmetade[1].push_back(2);
	for(int i = 3; i <= n; i++){
		if(isclokwise(1, 2, i)) qualmetade[1].push_back(i);
		else qualmetade[0].push_back(i);
	}
	for(int metade = 0; metade <= 1; metade++){
		sort(qualmetade[metade].begin(), qualmetade[metade].end(), comp);
		for(int i = 0; i < qualmetade[metade].size(); i++){
			int esse= qualmetade[metade][i];
			int tam = hull[metade].size();
			while(tam >= 2 && !isclokwise(hull[metade][tam - 2], hull[metade][tam - 1], esse)){
				tam--;
				hull[metade].pop_back();
			}
			hull[metade].push_back(esse);
		}
		if(metade)reverse(hull[1].begin(), hull[1].end());
		hull[metade].insert(hull[metade].begin(), 1);
	//hull[1].insert(hull[1].begin(), 1);

	}
	//printf("%d %d\n", hull[0].size(), hull[1].size() );
	if(min(hull[0].size(), hull[1].size()) == 2){
		giveans(max(hull[0].size(), hull[1].size()));
		//printf("oi\n");
		return 0;
	}

	for(int metade = 0; metade <= 1; metade++){
		hull[0].pop_back();
		while(true){
			bool quebra = true;
			int tam = hull[0].size();
			if(tam >= 2 && !isclokwise(hull[0][tam-2], hull[0][tam - 1], 
			hull[1][hull[1].size() - 1])){
				hull[0].pop_back();
				quebra = false;
			}
			tam = hull[1].size();
			if(tam >= 2 && !isclokwise(hull[0][hull[0].size() - 1], hull[1][tam-1], hull[1][tam - 2])){
				hull[1].pop_back();
				quebra = false;
			}
			if(quebra) break;
		}
		for(int i = 0; i <= 1; i++) reverse(hull[i].begin(), hull[i].end());
		swap(hull[0], hull[1]);
	}
	giveans(hull[0].size() + hull[1].size());
}

Compilation message (stderr)

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

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