Submission #134462

#	Time	Username	Problem	Language	Result	Execution time	Memory
134462		dragonslayerit	Triangles (CEOI18_tri)	C++14	100 / 100	1295 ms	2156 KiB

tri

#include "trilib.h"

#include <cstdio>
#include <algorithm>
#include <deque>

std::deque<int> hull;

void append(int p){
  while(hull.size()>=2&&is_clockwise(hull[hull.size()-2],hull[hull.size()-1],p)){
    hull.pop_back();
  }
  while(hull.size()>=2&&is_clockwise(hull[0],hull[1],p)){
    hull.pop_front();
  }
  hull.push_back(p);
}

template<class Iterator>
void insert(Iterator it,int p){
  std::rotate(hull.begin(),it,hull.end());
  append(p);
}

void add(int p){
  if(is_clockwise(hull[hull.size()-2],hull[hull.size()-1],p)){
    insert(hull.end()-1,p);
  }else if(is_clockwise(hull[hull.size()-1],hull[0],p)){
    insert(hull.end(),p);
  }else{
    int low=0,high=hull.size()-2;
    //clock(-1,low,p)=false
    //clock(-1,high,p)=true
    while(high-low>1){
      int mid=(low+high)/2;
      if(is_clockwise(hull[0],hull[mid],p)){
	high=mid;
      }else{
	low=mid;
      }
    }
    if(is_clockwise(hull[low],hull[high],p)){
      insert(hull.begin()+high,p);
    }
  }
}

int main(){
  int N=get_n();
  hull.push_back(1);
  hull.push_back(2);
  for(int i=3;i<=N;i++){
    add(i);
  }
  printf("%d\n",(int)hull.size());
}

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