Submission #161401

#TimeUsernameProblemLanguageResultExecution timeMemory
161401rama_pangTriangles (CEOI18_tri)C++14
100 / 100
33 ms2548 KiB
#include "trilib.h"
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N = get_n();
    vector<int> city;
    vector<int> left_city, right_city;

    for (int i = 2; i <= N - 1; i++) 
        if (is_clockwise(1, i, N))
            left_city.emplace_back(i);
        else
            right_city.emplace_back(i);
    
    auto cmp = [&](int l, int r) { return is_clockwise(1, l, r); };
    sort(left_city.begin(), left_city.end(), cmp);
    sort(right_city.begin(), right_city.end(), cmp);

    for (auto i : left_city) city.emplace_back(i);
    city.emplace_back(N);
    for (auto i : right_city) city.emplace_back(i);

    vector<int> hull;
    hull.emplace_back(1);

    for (auto i : city) {
        while (hull.size() >= 2 && !is_clockwise(hull[hull.size() - 2], hull[hull.size() - 1], i)) 
            hull.pop_back();

        hull.emplace_back(i);
    }

    while (hull.size() > 3) {
        if (!is_clockwise(hull[hull.size() - 1], hull[0], hull[1])) 
            hull.erase(hull.begin());
        else if (!is_clockwise(hull[hull.size() - 2], hull[hull.size() - 1], hull[0]))
            hull.pop_back();
        else 
            break;
    }

    give_answer(hull.size());
    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...