Submission #110773

#	Time	Username	Problem	Language	Result	Execution time	Memory
110773		IOrtroiii	Triangles (CEOI18_tri)	C++14	100 / 100	44 ms	2744 KiB

tri

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

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25