Submission #1175176

#TimeUsernameProblemLanguageResultExecution timeMemory
11751761binTriangles (CEOI18_tri)C++20
100 / 100
14 ms1988 KiB
#include <bits/stdc++.h>
#include "trilib.h"

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
int n;

// int get_n() {
//     int n; cin >> n;
//     return n;
// }
//
// bool is_clockwise(int a, int b, int c) {
//     cout << a << ' ' << b << ' ' <<c << endl;
//     int x; cin >> x;
//     return x;
// }
//
// void give_answer(int s) {
//     cout << s << endl;
// }

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    n = get_n();
    vector<int> U, D;
    for (int i = 3; i <= n; i++) {
        if (!is_clockwise(1, 2, i)) U.emplace_back(i);
        else D.emplace_back(i);
    }

    auto cmp = [&] (int a, int b) -> bool {
        return is_clockwise(1, a, b);
    };

    sort(all(U), cmp);
    U.insert(U.begin(), 1);
    U.emplace_back(2);
    sort(all(D), cmp);
    for (int& x : D) U.emplace_back(x);

    vector<int> hull;
    for (int& x : U) {
        while (hull.size() >= 2 && !is_clockwise(hull[hull.size() - 2], hull.back(), x)) hull.pop_back();
        hull.emplace_back(x);
    }
    int k = hull.size();
    for (int i = 0; i < k; i++) {
        while (hull.size() >= 2 && !is_clockwise(hull[hull.size() - 2], hull.back(), hull[i])) hull.pop_back();
        hull.emplace_back(hull[i]);
    }
    give_answer(hull.size() - k);
    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...