Submission #346511

#	Time	Username	Problem	Language	Result	Execution time	Memory
346511		wleung_bvg	Triangles (CEOI18_tri)	C++17	100 / 100	32 ms	2348 KiB

tri

#include "trilib.h"
#include <bits/stdc++.h>
using namespace std;
template<class C>constexpr int sz(const C&c){return int(c.size());}
using ll=long long;constexpr const char nl='\n',sp=' ';

namespace local_checker {
  vector<pair<ll, ll>> P;
  int query_count = 0;

  int get_n() {
    mt19937 rng(time(0));
    int N = 40000;
    for (int i = 0; i < N; i++) P.emplace_back(rng() % ll(1e9), rng() % ll(1e9));
    return N;
  }

  bool _clockwise_points(const pair<ll, ll> &a, const pair<ll, ll> &b, const pair<ll, ll> &c) {
    return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first) < 0;
  }

  bool is_clockwise(int a, int b, int c) {
    assert(query_count++ < 1e6);
    return _clockwise_points(P[a - 1], P[b - 1], P[c - 1]);
  }

  void give_answer(int s) {
    vector<pair<ll, ll>> hull;
    sort(P.begin(), P.end());
    for (int phase = 0; phase < 2; phase++) {
      for (int i = 0, st = sz(hull); i < sz(P); i++) {
        while (sz(hull) >= st + 2 && _clockwise_points(hull[sz(hull) - 2], hull[sz(hull) - 1], P[i])) hull.pop_back();
        hull.push_back(P[i]);
      }
      hull.pop_back(); reverse(P.begin(), P.end());
    }
    if (sz(hull) == 2 && hull[0] == hull[1]) hull.pop_back();
    if (hull.empty() && !P.empty()) hull.push_back(P[0]);
    cout << sz(hull) << sp << s << endl;
    assert(sz(hull) == s);
  }
}

// using namespace local_checker;

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // freopen("err.txt", "w", stderr);
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int N = get_n();
  int one = 1, two = 2;
  vector<vector<int>> side(2, vector<int>{two});
  for (int i = 1; i <= N; i++) if (i != one && i != two) side[is_clockwise(one, two, i)].push_back(i);
  for (int h = 0; h < 2; h++) {
    sort(side[h].begin(), side[h].end(), [&] (int i, int j) {
      return is_clockwise(one, i, j);
    });
    vector<int> temp;
    for (int i : side[h]) {
      while (sz(temp) >= 2 && !is_clockwise(temp[sz(temp) - 2], temp.back(), i)) temp.pop_back();
      temp.push_back(i);
    }
    side[h] = temp;
  }
  reverse(side[1].begin(), side[1].end());
  side[0].insert(side[0].begin(), one);
  side[0].pop_back();
  for (int h = 0; h < 2; h++) {
    bool done = false;
    while (!done) {
      done = true;
      for (int i = 0; i < 2; i++) {
        if (sz(side[h ^ i]) >= 2 && is_clockwise(side[h ^ i][sz(side[h ^ i]) - 2], side[h ^ i].back(), side[!(h ^ i)].back()) == i) {
          side[h ^ i].pop_back();
          done = false;
        }
      }
    }
    for (int i = 0; i < 2; i++) reverse(side[i].begin(), side[i].end());
  }
  give_answer(sz(side[0]) + sz(side[1]));
  return 0;
}

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