Submission #1176264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176264		dong_gas	Triangles (CEOI18_tri)	C++20	100 / 100	14 ms	1988 KiB

tri

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

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