Submission #585373

#TimeUsernameProblemLanguageResultExecution timeMemory
585373JomnoiTriangles (CEOI18_tri)C++17
100 / 100
24 ms2616 KiB
#include <bits/stdc++.h>
#include "trilib.h"
using namespace std;
 
bool cmp(const int &a, const int &b) {
    return is_clockwise(1, a, b) == false;
}

vector <int> convexHull(vector <int> cand) {
    vector <int> hull;
    for(auto x : cand) {
        while(hull.size() >= 2 and is_clockwise(hull[hull.size() - 2], hull.back(), x) == true) {
            hull.pop_back();
        }
        hull.push_back(x);
    }
    return hull;
}

int main() {
    int N = get_n();
    
    vector <int> L, R;
    for(int i = 3; i <= N; i++) {
        if(is_clockwise(1, 2, i) == true) {
            L.push_back(i);
        }
        else {
            R.push_back(i);
        }
    }

    sort(L.begin(), L.end(), cmp);
    sort(R.begin(), R.end(), cmp);
    L.push_back(2);
    R.push_back(1);

    L = convexHull(L), R = convexHull(R);

    vector <int> res;
    for(auto x : L) {
        res.push_back(x);
    }
    for(auto x : R) {
        res.push_back(x);
    }

    res = convexHull(res);

    deque <int> hull(res.begin(), res.end());
    bool ok = true;
    while(ok == true) {
        ok = false;

        int x = hull.back();
        hull.pop_back();
        if(is_clockwise(hull.back(), x, hull.front()) == true) {
            ok = true;
        }
        else {
            hull.push_back(x);
        }

        x = hull.front();
        hull.pop_front();
        if(is_clockwise(hull.front(), x, hull.back()) == false) {
            ok = true;
        }
        else {
            hull.push_front(x);
        }
    }
    give_answer(hull.size());
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...