Submission #1202906

#TimeUsernameProblemLanguageResultExecution timeMemory
1202906loomTriangles (CEOI18_tri)C++20
100 / 100
14 ms1352 KiB
#include<bits/stdc++.h>
#include "trilib.h"
using namespace std;
#define inf 5e18
#define nl '\n'

int P;
bool cmp(int a, int b){
   return is_clockwise(P, a, b);
}

deque<int> func(deque<int>& v, int p){
   P = p;
   sort(v.begin(), v.end(), cmp);
   deque<int> ans;
   ans.push_back(p);

   for(int x : v){
      while(ans.size() >= 2 and !is_clockwise(ans[ans.size()-2], ans.back(), x)) ans.pop_back();
      ans.push_back(x);
   }
   return ans;
}

inline void solve(){
   int n = get_n();

   deque<int> a, b;
   for(int i=3; i<=n; i++){
      (is_clockwise(1, 2, i) ? b : a).push_back(i);
   }
   
   a = func(a, 1);
   b = func(b, 2);

   for(int i=0; i<10; i++){
      while(a.size() >= 2 and b.size() >= 1 and !is_clockwise(b.back(), a[0], a[1])) a.pop_front();
      while(a.size() >= 1 and b.size() >= 2 and !is_clockwise(b[b.size()-2], b.back(), a[0])) b.pop_back();
      while(a.size() >= 1 and b.size() >= 2 and !is_clockwise(a.back(), b[0], b[1])) b.pop_front();
      while(a.size() >= 2 and b.size() >= 1 and !is_clockwise(a[a.size()-2], a.back(), b[0])) a.pop_back();
   }
   
   give_answer(a.size()+b.size());
}

signed main(){
   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 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...