Submission #205910

#	Time	Username	Problem	Language	Result	Execution time	Memory
205910		PeppaPig	Triangles (CEOI18_tri)	C++14	0 / 100	5 ms	508 KiB

tri

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

using namespace std;

void convex_hull(vector<int> &v) {
    int sz = 2;
    vector<int> ans = {v[0], v[1]};
    for(int i = 2; i < v.size(); i++) {
        while(sz > 1 && is_clockwise(ans[sz - 2], ans[sz - 1], v[i]))
            ans.pop_back(), --sz;
        ans.emplace_back(v[i]), ++sz;
    }
    v = ans;
}

int n;

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); });
    r.emplace_back(2), r.emplace_back(1);
    convex_hull(l), convex_hull(r);

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

    deque<int> ans(r.begin(), r.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;
}

Compilation message (stderr)

tri.cpp: In function 'void convex_hull(std::vector<int>&)':
tri.cpp:9:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 2; i < v.size(); i++) {
                    ~~^~~~~~~~~~

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