Submission #747851

#TimeUsernameProblemLanguageResultExecution timeMemory
747851amirhoseinfar1385Triangles (CEOI18_tri)C++17
0 / 100
1 ms324 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)!=is_clockwise(uu,u,2)){
    			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)!=is_clockwise(uu,u,1)){
    			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)!=is_clockwise(convt.front(),u,2)){
    			f=j;
    		}
    	}
    	for(int h=0;h<f;h++){
    		convb.pop_front();
    	}
    	if(f==0){
    		for(int j=1;j<(int)convt.size()-1;j++){
    			int u=convt[j-1];
    			int uu=convt[j];
    			if(is_clockwise(convb.front(),u,uu)!=is_clockwise(convb.front(),u,2)){
    				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)!=is_clockwise(convb.back(),u,1)){
    			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)!=is_clockwise(convt.back(),u,1)){
    				f=j;
    			}
    		}
    		for(;(int)convb.size()>f+1;){
    			convb.pop_back();
    		}	
    	}
    	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)!=is_clockwise(convt.front(),u,2)){
    			f=j;
    		}
    	}
    	for(int h=0;h<f;h++){
    		convb.pop_front();
    	}
    	if(f==0){
    		for(int j=1;j<(int)convt.size()-1;j++){
    			int u=convt[j-1];
    			int uu=convt[j];
    			if(is_clockwise(convb.front(),u,uu)!=is_clockwise(convb.front(),u,2)){
    				f=j;
    			}
    		}	
    		for(int h=0;h<f;h++){
    			convt.pop_front();
    		}	
    	}
    	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)!=is_clockwise(convb.back(),u,1)){
    			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)!=is_clockwise(convt.back(),u,1)){
    				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:11: warning: variable 'f' set but not used [-Wunused-but-set-variable]
   32 |       int f=0;
      |           ^
tri.cpp:49:11: 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...