Submission #747843

#	Time	Username	Problem	Language	Result	Execution time	Memory
747843		amirhoseinfar1385	Triangles (CEOI18_tri)	C++17	0 / 100	1 ms	212 KiB

tri

#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();
			}
		}
		if(f){
			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();
			}
		}
		if(f){
			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();
		}	
	}
	//cout<<convb.size()<<" "<<convt.size()<<endl;
	int ret=(int)convb.size()+convt.size();
		give_answer(ret);
		return 0;	
}

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