Submission #572122

#TimeUsernameProblemLanguageResultExecution timeMemory
572122piOOETriangles (CEOI18_tri)C++17
0 / 100
1 ms332 KiB
#include <bits/stdc++.h>
#include "trilib.h"

using namespace std;

#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }

const int N = 40000;
const ll infL = 3e18;

int n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    n = get_n();
    vector<int> ord(n);
    iota(all(ord), 0);
    stable_sort(1 + all(ord), [](int i, int j) {
        return !is_clockwise(1, i + 1, j + 1);
    });
    vector<int> st;
    for (int i : ord) {
        while (sz(st) > 1 && is_clockwise(st.end()[-2] + 1, st.back() + 1, i + 1)) {
            st.pop_back();
        }
        st.push_back(i);
    }
    rotate(begin(st), begin(st) + sz(st) - 2, end(st));
    ord = st;
    st.clear();

    for (int i : ord) {
        while (sz(st) > 1 && is_clockwise(st.end()[-2] + 1, st.back() + 1, i + 1)) {
            st.pop_back();
        }
        st.push_back(i);
    }
    give_answer(sz(st));
    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...