Submission #1175176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175176		1bin	Triangles (CEOI18_tri)	C++20	100 / 100	14 ms	1988 KiB

tri

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

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