Submission #400998

#	Time	Username	Problem	Language	Result	Execution time	Memory
400998		KoD	Triangles (CEOI18_tri)	C++17	100 / 100	28 ms	2556 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"

template <class T>
using Vec = std::vector<T>;

using ll = long long;

int main() {
    const int N = get_n();
    Vec<int> upper, lower;
    for (int i = 3; i <= N; ++i) {
        (is_clockwise(1, 2, i) ? lower : upper).push_back(i);
    }
    std::sort(upper.begin(), upper.end(), [&](const int i, const int j) {
        return !is_clockwise(1, i, j);
    });
    std::sort(lower.begin(), lower.end(), [&](const int i, const int j) {
        return !is_clockwise(1, i, j);
    });
    Vec<int> order;
    const auto add =[&](const int i) {
        while (order.size() >= 2 and is_clockwise(order[order.size() - 2], order[order.size() - 1], i)) {
            order.pop_back();
        }
        order.push_back(i);
    };
    upper.insert(upper.begin(), 2);
    upper.insert(upper.end(), 1);
    for (const auto x: upper) {
        add(x);
    }
    for (const auto x: lower) {
        add(x);       
    }
    const auto cur = order.size();
    for (const auto x: upper) {
        add(x);
    }
    for (const auto x: lower) {
        add(x);       
    }
    give_answer(order.size() - cur);
    return 0;
}

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