Submission #225809

#	Time	Username	Problem	Language	Result	Execution time	Memory
225809		kshitij_sodani	Triangles (CEOI18_tri)	C++17	100 / 100	34 ms	2716 KiB

tri

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#include "trilib.h"
#define pb push_back
#define a first
#define b second
typedef long long llo;
/*bool is_clockwise(int i,int j,int k){
	cout<<i<<" "<<j<<" "<<k<<endl;
	int x;
	cin>>x;
	if(x){
		return true;
	}
	else{
		return false;
	}
}
int get_n(){
	return 6;
}
void give_answer(int nn){
	cout<<nn<<":"<<endl;
}*/
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n=get_n();
	int vis[n];
	for(int i=0;i<n;i++){
		vis[i]=1;
	}
	vector<int> no;
	vector<int> no2;

	for(int i=2;i<n;i++){
		if(is_clockwise(1,2,i+1)){
			no.pb(i+1);
		//	cout<<i<<endl;
		}
		else{
			no2.pb(i+1);
		}
	}
	no.pb(2);
	no2.pb(2);
	vector<int> hull;
	stable_sort(no.begin(), no.end(), [&](const int &p, const int &q) { return is_clockwise(1, p, q); });
	stable_sort(no2.begin(), no2.end(), [&](const int &p, const int &q) { return !is_clockwise(1, p, q); });
	no.insert(no.begin(),1);
	for(auto jj:no){
		while(hull.size()>1 and !is_clockwise(hull[hull.size()-2],hull[hull.size()-1],jj)){
			hull.pop_back();
		}
		hull.pb(jj);
	}
	vector<int> hull2;
/*	hull2.pb(1);
	hull2.pb(2);*/
	no2.insert(no2.begin(),1);
	for(auto jj:no2){
		while(hull2.size()>1 and is_clockwise(hull2[hull2.size()-2],hull2[hull2.size()-1],jj)){
			hull2.pop_back();
		}
		hull2.pb(jj);
	}

	int k,l;
	vector<int> hull3;
	for(int i=1;i<hull.size();i++){
		hull3.pb(hull[i]);
	}
	hull3.pb(1);
	for(int i=hull2.size()-1;i>=2;i--){
		hull3.pb(hull2[i]);
	}
	deque<int> fin;
	fin.pb(2);
	for(auto jj:hull3){
		if(jj==2){
			continue;
		}
		while(fin.size()>1 and !is_clockwise(fin[fin.size() - 2],fin[fin.size() - 1],jj)){
			fin.pop_back();
		}
		fin.push_back(jj);
	}
	while(fin.size()>3){
		if(!is_clockwise(fin[fin.size() - 1], fin[0], fin[1])){
			fin.pop_front();
		}
		else if(!is_clockwise(fin[fin.size() - 2], fin[fin.size() - 1], fin[0])){
			fin.pop_back();
		}
		else{
			break;
		}
	}

	give_answer(fin.size());




	return 0;
}

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:71:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<hull.size();i++){
              ~^~~~~~~~~~~~
tri.cpp:30:6: warning: variable 'vis' set but not used [-Wunused-but-set-variable]
  int vis[n];
      ^~~
tri.cpp:69:6: warning: unused variable 'k' [-Wunused-variable]
  int k,l;
      ^
tri.cpp:69:8: warning: unused variable 'l' [-Wunused-variable]
  int k,l;
        ^

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