제출 #585373

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585373		Jomnoi	Triangles (CEOI18_tri)	C++17	100 / 100	24 ms	2616 KiB

tri

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

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