Submission #110773

#TimeUsernameProblemLanguageResultExecution timeMemory
110773IOrtroiiiTriangles (CEOI18_tri)C++14
100 / 100
44 ms2744 KiB
#include <bits/stdc++.h>
#include "trilib.h"
using namespace std;

bool cmp(int u,int v) {
   return is_clockwise(1, u, v);
}

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)) {
         R.push_back(i);
      } else {
         L.push_back(i);
      }
   }

   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() - 2], p.back(), id)) p.pop_back();
      p.push_back(id);
   }
   for (int id : R) {
      while (p.size() > 1 && !is_clockwise(p[p.size() - 2], 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() - 2], p.back(), id)) p.pop_back();
      p.push_back(id);
   }
   for (int id : R) {
      while (p.size() > 1 && !is_clockwise(p[p.size() - 2], 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...