Submission #960538

#TimeUsernameProblemLanguageResultExecution timeMemory
960538vjudge1Triangles (CEOI18_tri)C++14
75 / 100
21 ms2964 KiB
#include "trilib.h"

#include<bits/stdc++.h>

using namespace std;

int n;

vector<int> convex_hull(vector<int> v){
   vector<int> v2;
   for (int i:v){
      while ((int)v2.size()>=2 && is_clockwise(v2.end()[-2], v2.end()[-1], i)) v2.pop_back();
      v2.push_back(i);
   }
   return v2;
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   n=get_n();
   vector<int> v(n);
   iota(v.begin(), v.end(), 1);
   vector<vector<int>> vv(2);
   for (int i=2; i<n; ++i) vv[is_clockwise(v[0], v[1], v[i])].push_back(v[i]);
   vv[0].push_back(v[1]);
   vv[1].push_back(v[1]);
   sort(vv[0].begin(), vv[0].end(), [&](int x, int y){
      return !is_clockwise(v[0], x, y);
   });
   sort(vv[1].begin(), vv[1].end(), [&](int x, int y){
      return !is_clockwise(v[0], x, y);
   });
   vv[0].insert(vv[0].begin(), v[0]);
   vv[1].insert(vv[1].begin(), v[0]);
   vv[0]=convex_hull(vv[0]);
   vv[1]=convex_hull(vv[1]);
   bool rev=0;
   if (vv[0].back()!=v[1]) reverse(vv[0].begin()+1, vv[0].end()), rev=1;
   if (vv[1].back()!=v[1]) reverse(vv[1].begin()+1, vv[0].end());
   else rev=1;
   v.swap(vv[0]);
   v.insert(v.end(), vv[1].rbegin()+1, vv[1].rend()-1);
   if (rev) reverse(v.begin()+1, v.end());
   vector<int> v2;
   for (int i:v){
      while ((int)v2.size()>=2 && is_clockwise(v2.end()[-2], v2.end()[-1], i)) v2.pop_back();
      v2.push_back(i);
   }
   for (int i:v){
      while ((int)v2.size()>=2 && is_clockwise(v2.end()[-2], v2.end()[-1], i)) v2.pop_back();
      v2.push_back(i);
   }
   vector<int> cnt(n+1);
   for (int i:v2) ++cnt[i];
   while (cnt[v2.back()]==1) v2.pop_back();
   reverse(v2.begin(), v2.end());
   while (cnt[v2.back()]==1) v2.pop_back();
   give_answer((int)v2.size()/2);
   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...