제출 #679897

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
679897		mjhmjh1104	Triangles (CEOI18_tri)	C++17	0 / 100	1 ms	288 KiB

tri

#include "trilib.h"
#include <vector>
#include <algorithm>
using namespace std;

int ccw(int x, int y, int z) {
    bool t = is_clockwise(x + 1, y + 1, z + 1);
    return t ? -1 : 1;
}

void _sort(vector<int> &v, int l, int r, bool counterclockwise) {
    if (l >= r) return;
    int m = (l + r) / 2;
    _sort(v, l, m, counterclockwise);
    _sort(v, m + 1, r, counterclockwise);
    vector<int> u;
    int x = l, y = m + 1;
    while (x <= m && y <= r) {
        if ((ccw(v[x], v[0], v[y]) > 0) ^ counterclockwise) u.push_back(v[x++]);
        else u.push_back(v[y++]);
    }
    while (x <= m) u.push_back(v[x++]);
    while (y <= r) u.push_back(v[y++]);
    for (int i = 0; i < (int)u.size(); i++) v[l + i] = u[i];
}

vector<int> hull(vector<int> &v, bool counterclockwise) {
    vector<int> st;
    st.push_back(0);
    st.push_back(1);
    for (int i = 2; i < (int)v.size(); i++) {
        while ((int)st.size() > 1) {
            int first = st.back(); st.pop_back();
            int second = st.back();
            if ((ccw(v[second], v[first], v[i]) < 0) ^ counterclockwise) {
                st.push_back(first);
                break;
            }
        }
        st.push_back(i);
    }
    vector<int> res;
    for (auto &i: st) res.push_back(v[i]);
    return res;
}

int main() {
    int n = get_n();
    vector<int> a, b;
    a = { 0, 1 };
    b = { 0, 1 };
    for (int i = 2; i < n; i++) {
        if (ccw(0, 1, i) > 0) a.push_back(i);
        else b.push_back(i);
    }
    _sort(a, 1, (int)a.size() - 1, 1);
    _sort(b, 1, (int)b.size() - 1, 0);
    vector<int> x = hull(a, 1);
    vector<int> y = hull(b, 0);
    vector<int> z;
    z.push_back(0);
    reverse(a.begin(), a.end());
    for (auto &i: x) if (i > 1) z.push_back(i);
    z.push_back(1);
    for (auto &i: y) if (i > 1) z.push_back(i);
    give_answer((int)hull(z, 0).size());
}

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