Submission #679921

#	Time	Username	Problem	Language	Result	Execution time	Memory
679921		mjhmjh1104	Triangles (CEOI18_tri)	C++17	0 / 100	0 ms	212 KiB

tri

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

int ccw(int x, int y, int z) {
    return is_clockwise(x + 1, y + 1, z + 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];
}

int hull(vector<int> &v) {
    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) {
                st.push_back(first);
                break;
            }
        }
        st.push_back(i);
    }
    int k = 0;
    while ((int)st.size() - k > 3) {
        while ((int)st.size() - k > 3 && k + 1 < (int)st.size() && ccw(v[st.back()], v[st[k]], v[st[k + 1]]) > 0) k++;
        if ((int)st.size() - k > 3 && (int)st.size() > 1 && ccw(v[st[(int)st.size() - 2]], v[st.back()], v[st[k]]) > 0) st.pop_back();
        else break;
    }
    return (int)st.size() - k;
}

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> z;
    z.push_back(0);
    reverse(a.begin(), a.end());
    for (auto &i: a) if (i > 1) z.push_back(i);
    z.push_back(1);
    for (auto &i: b) if (i > 1) z.push_back(i);
    give_answer(hull(z));
}

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