Submission #161402

#	Time	Username	Problem	Language	Result	Execution time	Memory
161402		rama_pang	Triangles (CEOI18_tri)	C++14	100 / 100	45 ms	2040 KiB

tri

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

    deque<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.pop_front();
        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;
}

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