Submission #841824

#	Time	Username	Problem	Language	Result	Execution time	Memory
841824		WLZ	Triangles (CEOI18_tri)	C++17	100 / 100	22 ms	2396 KiB

tri

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

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