Submission #205921

#	Time	Username	Problem	Language	Result	Execution time	Memory
205921		PeppaPig	Triangles (CEOI18_tri)	C++14	100 / 100	39 ms	2480 KiB

tri

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

using namespace std;

int n;

void convex_hull(vector<int> &v) {
    vector<int> ans;
    for(int x : v) {
        while(ans.size() > 1 && !is_clockwise(ans[ans.size() - 2], ans.back(), x))
            ans.pop_back();
        ans.emplace_back(x);
    }
    v = ans;
}

int main() {
    n = get_n();
    vector<int> l, r;
    for(int i = 3; i <= n; i++) {
        if(!is_clockwise(1, 2, i)) l.emplace_back(i);
        else r.emplace_back(i);
    }
    sort(l.begin(), l.end(), [&](int &a, int &b) { return is_clockwise(1, a, b); });
    sort(r.begin(), r.end(), [&](int &a, int &b) { return is_clockwise(1, a, b); });
    l.emplace_back(2), r.emplace_back(1);
    convex_hull(l), convex_hull(r);

    for(int x : r) l.emplace_back(x);
    convex_hull(l);

    deque<int> ans(l.begin(), l.end());
    while(true) {
        bool valid = true;
        if(!is_clockwise(ans[ans.size() - 2], ans.back(), ans.front()))
            ans.pop_back(), valid = false;
        if(is_clockwise(ans[1], ans[0], ans.back()))
            ans.pop_front(), valid = false;
        if(valid) break;
    }

    give_answer(ans.size());

    return 0;
}

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