Submission #951178

#	Time	Username	Problem	Language	Result	Execution time	Memory
951178		glebustim	Triangles (CEOI18_tri)	C++17	20 / 100	1 ms	348 KiB

tri

#include "trilib.h"
//#include "trilib.c"
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
using oset = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

random_device rd;
mt19937 rnd(rd());

bool is_inside(int a, int b, int c, int d) {
    bool x = is_clockwise(a, b, d), y = is_clockwise(b, c, d), z = is_clockwise(c, a, d);
    return (x == y && y == z);
}

int O;

bool comp(int x, int y) {
    return is_clockwise(O, y, x);
}

int main() {
    int n = get_n();
    vi r(n);
    iota(all(r), 1);
    shuffle(all(r), rnd);
    int a = r[0], b = r[1], c = r[2];
    for (int i = 3; i < n; ++i) {
        if (!is_clockwise(a, b, c))
            swap(b, c);
        if (is_clockwise(a, b, r[i])) {
            if (is_inside(a, b, r[i], c))
                c = r[i];
        }
        else if (is_clockwise(b, c, r[i])) {
            if (is_inside(b, c, r[i], a))
                a = r[i];
        }
        else if (is_inside(a, c, r[i], b))
            b = r[i];
    }
    O = a;
    vi p(n - 1);
    for (int i = 1; i < O; ++i)
        p[i - 1] = i;
    for (int i = O + 1; i <= n; ++i)
        p[i - 2] = i;
    sort(all(p), comp);
    vi st;
    st.push_back(O);
    for (int i: p) {
        while (st.size() > 1 && is_clockwise(st[(int)st.size() - 2], st.back(), i))
            st.pop_back();
        st.push_back(i);
    }
    give_answer((int)st.size());
}

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