Submission #1176264

#TimeUsernameProblemLanguageResultExecution timeMemory
1176264dong_gasTriangles (CEOI18_tri)C++20
100 / 100
14 ms1988 KiB
#include <bits/stdc++.h>
#include "trilib.h"
using namespace std;
const int MAXN = 4e4 + 4;

int n;


int main(void) {
    cin.tie(0)->sync_with_stdio(0);

    n = get_n();
    vector<int> up = {2}, lo, hull;
    for (int i = 3; i <= n; i++) {
        if (is_clockwise(1, 2, i)) lo.push_back(i);
        else up.push_back(i);
    }
    sort(up.begin(), up.end(), [&](int a, int b) { return !is_clockwise(1, a, b); });
    sort(lo.begin(), lo.end(), [&](int a, int b) { return !is_clockwise(1, a, b); });
    up.push_back(1);
    for (int i: lo) up.push_back(i);
    for (int i: up) {
        while (hull.size() >= 2 && is_clockwise(hull[hull.size() - 2], hull.back(), i)) hull.pop_back();
        hull.push_back(i);
    }
    int cnt = hull.size();
    for (int i = 0; i < cnt; i++) {
        while (hull.size() >= 2 && is_clockwise(hull[hull.size() - 2], hull.back(), hull[i])) hull.pop_back();
        hull.push_back(hull[i]);
    }
    give_answer(hull.size() - cnt);
    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...