Submission #747858

#	Time	Username	Problem	Language	Result	Execution time	Memory
747858		amirhoseinfar1385	Triangles (CEOI18_tri)	C++17	100 / 100	22 ms	1780 KiB

tri

#include<bits/stdc++.h>
#include "trilib.h"
using namespace std;
vector<int>res;

bool cmp(int a,int b){
	return is_clockwise(1,a,b);
}

void add(int i){
	if((int)res.size()<=1){
		res.push_back(i);
		return;
	}
	while((int)res.size()>1){
		if(is_clockwise(res[(int)res.size()-2],res.back(),i)){
			break;
		}
		else{
			res.pop_back();
		}
	}
	res.push_back(i);
//	cout<<i<<" "<<res.size()<<"\n";
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n=get_n();
	vector<int>top,bot;
	for(int i=3;i<=n;i++){
		if(is_clockwise(1,2,i)){
			bot.push_back(i);
		}
		else{
			top.push_back(i);
		}
	}
	sort(top.begin(),top.end(),cmp);
	sort(bot.begin(),bot.end(),cmp);
	add(1);
	for(auto x:top){
		add(x);
	}
	add(2);
	for(auto x:bot){
		add(x);
	}
	int first=res.size();
	add(1);
	for(auto x:top){
		add(x);
	}
	add(2);
	for(auto x:bot){
		add(x);
	}
	int ret=(int)res.size();
	ret-=first;
	give_answer(ret);
	return 0;
}

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