Submission #747849

#TimeUsernameProblemLanguageResultExecution timeMemory
747849amirhoseinfar1385Triangles (CEOI18_tri)C++17
0 / 100
1 ms340 KiB
#include<bits/stdc++.h>
#include "trilib.h"
using namespace std;

bool cmp(int a,int b){
	return is_clockwise(1,a,b);
}
 
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);
	reverse(bot.begin(),bot.end());
	deque<int>convb,convt;
	for(int i=0;i<(int)top.size();i++){
		if((int)convt.size()<=1){
			convt.push_back(top[i]);
			continue;
		}
		int f=0;
		while((int)convt.size()>1){
			if(is_clockwise(convt[(int)convt.size()-2],convt.back(),top[i])){
				break;
			}
			else{
				f=1;
				convt.pop_back();
			}
		}
		convt.push_back(top[i]);
	}
	for(int i=0;i<(int)bot.size();i++){
		if((int)convb.size()<=1){
			convb.push_back(bot[i]);
			continue;
		}
		int f=0;
		while((int)convb.size()>1){
			if(!is_clockwise(convb[(int)convb.size()-2],convb.back(),bot[i])){
				break;
			}
			else{
				f=1;
				convb.pop_back();
			}
		}
		convb.push_back(bot[i]);
	}
	while((int)convb.size()>1){
		int u=convb.front();
		int uu=convb[1];
		if(is_clockwise(uu,u,1)){
			convb.pop_front();
		}
		else{
			break;
		}
	}
	while((int)convt.size()>1){
		int u=convt.back();
		int uu=convt[(int)convt.size()-2];
		if(!is_clockwise(uu,u,2)){
			convt.pop_back();
		}
		else{
			break;
		}
	}
	convb.push_front(1);
	convt.push_back(2);
	if((int)convb.size()==1||(int)convt.size()==1){
		int ret=(int)convb.size()+(int)convt.size();
		give_answer(ret);
		return 0;
	}
/*	cout<<top.size()<<" "<<bot.size()<<endl;
	for(auto x:top){
		cout<<x<<" ";
	}
	cout<<endl;
	for(auto x:bot){
		cout<<x<<" ";
	}
	cout<<endl;*/
	int f=0;
	for(int j=1;j<(int)convb.size();j++){
		int u=convb[j-1];
		int uu=convb[j];
		if(is_clockwise(convt.front(),u,uu)){
			f=j;
		}
	}
	for(int h=0;h<f;h++){
		convb.pop_front();
	}
	if(f==0){
		for(int j=1;j<(int)convt.size();j++){
			int u=convt[j-1];
			int uu=convt[j];
			if(!is_clockwise(convb.front(),u,uu)){
				f=j;
			}
		}	
		for(int h=0;h<f;h++){
			convt.pop_front();
		}	
	}
	int z=0;
	f=(int)convt.size()-1;
	for(int j=(int)convt.size()-2;j>=0;j--){
		int u=convt[j+1];
		int uu=convt[j];
		if(is_clockwise(convb.back(),u,uu)){
			f=j;
			z=1;
		}
	}
	for(;(int)convt.size()>f+1;){
		convt.pop_back();
	}
	if(z==0){
		f=(int)convb.size()-1;
		for(int j=(int)convb.size()-2;j>=0;j--){
			int u=convb[j+1];
			int uu=convb[j];
			if(!is_clockwise(convt.back(),u,uu)){
				f=j;
			}
		}
		for(;(int)convb.size()>f+1;){
			convb.pop_back();
		}	
	}
	//cout<<convb.size()<<" "<<convt.size()<<endl;
	int ret=(int)convb.size()+convt.size();
		give_answer(ret);
		return 0;	
}

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:32:7: warning: variable 'f' set but not used [-Wunused-but-set-variable]
   32 |   int f=0;
      |       ^
tri.cpp:49:7: warning: variable 'f' set but not used [-Wunused-but-set-variable]
   49 |   int f=0;
      |       ^
#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...