Submission #951190

#TimeUsernameProblemLanguageResultExecution timeMemory
951190glebustimTriangles (CEOI18_tri)C++17
0 / 100
1 ms604 KiB
#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 comp(int x, int y) {
    return is_clockwise(1, 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);
    }
    sort(all(a), comp);
    sort(all(b), comp);
    vi c = {1};
    for (int i: a)
        c.push_back(i);
    c.push_back(2);
    for (int i: b)
        c.push_back(i);
    vi st;
    for (int i: c) {
        while (st.size() > 1 && is_clockwise(st[(int)st.size() - 2], st.back(), i))
            st.pop_back();
        st.push_back(i);
    }
    for (int i: c) {
        while (st.size() > 1 && is_clockwise(st[(int)st.size() - 2], st.back(), i))
            st.pop_back();
        st.push_back(i);
    }
    vi cnt(n, 0);
    int ans = 0;
    for (int i: st) {
        ++cnt[i];
        if (cnt[i] == 2)
            ++ans;
    }
    give_answer(ans);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...