Submission #110763

#TimeUsernameProblemLanguageResultExecution timeMemory
110763IOrtroiiiTriangles (CEOI18_tri)C++14
0 / 100
3 ms512 KiB
#include <bits/stdc++.h>
#include "trilib.h"
using namespace std;

int main() {
   int n = get_n();
   vector<int> L, R;
   L.push_back(2);
   for (int i = 3; i <= n; ++i) {
      if (is_clockwise(1, 2, i)) {
         L.push_back(i);
      } else {
         R.push_back(i);
      }
   }
   auto cmp = [&](int u,int v) {
      return is_clockwise(1, u, v);
   };
   sort(L.begin(), L.end(), cmp);
   sort(R.begin(), R.end(), cmp);
   L.insert(L.begin(), 1);
   vector<int> p;
   for (int id : L) {
      while (p.size() > 1 && !is_clockwise(p[p.size() - 1], p.back(), id)) p.pop_back();
      p.push_back(id);
   }
   for (int id : R) {
      while (p.size() > 1 && !is_clockwise(p[p.size() - 1], p.back(), id)) p.pop_back();
      p.push_back(id);
   }
   int sv = p.size();
   for (int id : L) {
      while (p.size() > 1 && !is_clockwise(p[p.size() - 1], p.back(), id)) p.pop_back();
      p.push_back(id);
   }
   for (int id : R) {
      while (p.size() > 1 && !is_clockwise(p[p.size() - 1], p.back(), id)) p.pop_back();
      p.push_back(id);
   }
   give_answer(p.size() - sv);
}
#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...