Submission #572082

#TimeUsernameProblemLanguageResultExecution timeMemory
572082piOOETriangles (CEOI18_tri)C++17
0 / 100
1 ms212 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();
    multiset<int> st;
    for (int s = 0; s < 3; ++s) {
        //pseudo Jarvis algorithm
        int p0 = s, pi = s;
        int k = 0;
        do {
            ++k;
            pi = -1;
            for (int i = 0; i < n; ++i) {
                if (p0 != i && (pi == -1 || is_clockwise(p0 + 1, pi + 1, i + 1))) {
                    pi = i;
                }
            }
            p0 = pi;
        } while (pi != s || k <= n);
        if (k > n) {
            cout << n - 1;
            return 0;
        }
        st.insert(k);
    }
    if (st.count(*st.begin()) >= 2) {
        cout << *st.begin();
    } else {
        cout << *st.rbegin();
    };
    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...