Submission #951192

#	Time	Username	Problem	Language	Result	Execution time	Memory
951192		glebustim	Triangles (CEOI18_tri)	C++17	20 / 100	1 ms	600 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>;

bool is_not_inside(vi &a, int i) {
    if (a.size() < 3)
        return true;
    for (int j = 0; j < (int)a.size(); ++j) {
        if (is_clockwise(a[j], a[(j + 1) % (int)a.size()], i))
            return true;
    }
    return false;
}

int O;

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

int main() {
    int n = get_n();
    vi a, b;
    for (int i = 3; i <= n; ++i) {
        if (is_clockwise(1, 2, i))
            a.push_back(i);
        else
            b.push_back(i);
    }
    O = 2;
    sort(all(a), comp);
    O = 1;
    sort(all(b), comp);
    vi st1 = {2, 1};
    for (int i: a) {
        while (is_clockwise(st1[(int)st1.size() - 2], st1.back(), i))
            st1.pop_back();
        st1.push_back(i);
    }
    vi st2 = {1, 2};
    for (int i: b) {
        while (is_clockwise(st2[(int)st2.size() - 2], st2.back(), i))
            st2.pop_back();
        st2.push_back(i);
    }
    vi c = {1};
    for (int i = 2; i < (int)st1.size(); ++i)
        c.push_back(st1[i]);
    c.push_back(2);
    for (int i = 2; i < (int)st2.size(); ++i)
        c.push_back(st2[i]);
    int ans = (int)c.size();
    for (int i = 0; i < (int)c.size(); ++i) {
        if (is_clockwise(c[i], c[(i + 1) % (int)c.size()], c[(i + 2) % (int)c.size()]))
            --ans;
    }
    give_answer(ans);
}

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