Submission #205898

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

tri

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

using namespace std;

void convex_hull(vector<int> &v) {
    sort(next(v.begin()), v.end(), [&](const int &a, const int &b) {
        return is_clockwise(v[0], a, b);
    });
    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 = {1, 2}, r = {1, 2};
    for(int i = 3; i <= n; i++) {
        if(is_clockwise(1, 2, i)) l.emplace_back(i);
        else r.emplace_back(i);
    }
    convex_hull(l), convex_hull(r);
    for(int x : l) if(x != 1 && x != 2) 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:12: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