Submission #400999

#	Time	Username	Problem	Language	Result	Execution time	Memory
400999		KoD	Triangles (CEOI18_tri)	C++17	100 / 100	25 ms	1880 KiB

tri

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

bool cmp(int i, int j) { return !is_clockwise(1, i, j); }

int main() {
    int N = get_n();
    std::vector<int> up, lo, pt;
    up.push_back(2);
    for (int i = 3; i <= N; ++i) (is_clockwise(1, 2, i) ? lo : up).push_back(i);
    std::sort(up.begin(), up.end(), cmp);
    std::sort(lo.begin(), lo.end(), cmp);
    up.push_back(1);
    for (int x: lo) up.push_back(x);
    auto add = [&](int i) {
        while (pt.size() >= 2 and is_clockwise(pt[pt.size() - 2], pt.back(), i)) pt.pop_back();
        pt.push_back(i);
    };
    for (int x: up) add(x); 
    int cur = pt.size();
    for (int x: up) add(x);
    give_answer(pt.size() - cur);
    return 0;
}

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