Submission #747856

#TimeUsernameProblemLanguageResultExecution timeMemory
747856amirhoseinfar1385Triangles (CEOI18_tri)C++17
0 / 100
0 ms212 KiB
#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){
		int u=res.back();
		int uu=res[(int)res.size()-2];
		if(is_clockwise(uu,u,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();
	deque<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 ret;
}
#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...