Submission #1202505

#TimeUsernameProblemLanguageResultExecution timeMemory
1202505loomTriangles (CEOI18_tri)C++20
0 / 100
1 ms528 KiB
#include<bits/stdc++.h>
#include "trilib.h"
using namespace std;
#define inf 5e18
#define nl '\n'
 
int p = 1, q = 2;

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

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

   set<int> st;
   for(int i=3; i<=n; i++){
      if(!is_clockwise(p, q, i)){
         st.insert(i);
         continue;
      }
      q = i;

      for(int j : st){
         if(is_clockwise(p, q, j)) p = j;
      }
   }

   vector<int> v;
   for(int i=1; i<=n; i++) if(i != p) v.push_back(i);
   sort(v.begin(), v.end(), cmp);

   vector<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);
   }

   give_answer(ans.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...