Submission #841824

#TimeUsernameProblemLanguageResultExecution timeMemory
841824WLZTriangles (CEOI18_tri)C++17
100 / 100
22 ms2396 KiB
#include "trilib.h"
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n = get_n();
  vector<int> upper, lower;
  for (int i = 3; i <= n; i++) {
    if (is_clockwise(2, 1, i)) upper.push_back(i);
    else lower.push_back(i);
  }
  sort(upper.begin(), upper.end(), [&](int a, int b) {
    return is_clockwise(1, a, b);
  });
  vector<int> upper_hull = {1};
  upper.push_back(2);
  for (auto &i : upper) {
    while ((int) upper_hull.size() >= 2 && is_clockwise(i, upper_hull.back(), upper_hull[(int) upper_hull.size() - 2])) upper_hull.pop_back();
    upper_hull.push_back(i);
  }
  sort(lower.begin(), lower.end(), [&](int a, int b) {
    return is_clockwise(2, a, b);
  });
  lower.push_back(1);
  vector<int> lower_hull = {2};
  for (auto &i : lower) {
    while ((int) lower_hull.size() >= 2 && is_clockwise(i, lower_hull.back(), lower_hull[(int) lower_hull.size() - 2])) lower_hull.pop_back();
    lower_hull.push_back(i);
  }
  reverse(lower_hull.begin(), lower_hull.end());
  upper_hull.pop_back();
  while (1) {
    if ((int) lower_hull.size() >= 2 && (int) upper_hull.size() >= 1 && is_clockwise(lower_hull[(int) lower_hull.size() - 2], lower_hull.back(), 
    upper_hull.back())) {
      lower_hull.pop_back();
      continue;
    }
    if ((int) upper_hull.size() >= 2 && (int) lower_hull.size() >= 1 && is_clockwise(lower_hull.back(), upper_hull.back(),
    upper_hull[(int) upper_hull.size() - 2])) {
      upper_hull.pop_back();
      continue;
    }
    break;
  }
  reverse(lower_hull.begin(), lower_hull.end());
  reverse(upper_hull.begin(), upper_hull.end());
  upper_hull.pop_back();
  while (1) {
    if ((int) lower_hull.size() >= 2 && (int) upper_hull.size() >= 1 && is_clockwise(lower_hull.back(), lower_hull[(int) lower_hull.size() - 2]
    , upper_hull.back())) {
      lower_hull.pop_back();
      continue;
    }
    if ((int) upper_hull.size() >= 2 && (int) lower_hull.size() >= 1 && is_clockwise(lower_hull.back(), upper_hull[(int) upper_hull.size() - 2],
    upper_hull.back())) {
      upper_hull.pop_back();
      continue;
    }
    break;
  }
  give_answer((int) lower_hull.size() + (int) upper_hull.size());
  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...