Submission #1350166

#TimeUsernameProblemLanguageResultExecution timeMemory
1350166biankTriangles (CEOI18_tri)C++20
100 / 100
12 ms1600 KiB
#include <bits/stdc++.h>
#include "trilib.h"
 
using namespace std;
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
 
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vb = vector<bool>;
using pll = pair<ll, ll>;

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

#define pb push_back
#define eb emplace_back

#define fst first
#define snd second

void mySort(vi &a, auto cmp) {
    const int n = sz(a);
    if (n <= 1) return;
    vi l(begin(a), begin(a) + n / 2);
    vi r(begin(a) + n / 2, end(a));
    mySort(l, cmp), mySort(r, cmp);
    int i = 0, j = 0;
    forn(k, n) {
        if (j == sz(r) || (i < sz(l) && cmp(l[i], r[j]))) a[k] = l[i++];
        else a[k] = r[j++];
    }
}

vi buildHull(vi &points) {
    vi hull;
    for (int i : points) {
        while (sz(hull) >= 2 && !is_clockwise(end(hull)[-2], end(hull)[-1], i)) hull.pop_back();
        hull.pb(i);
    }
    return hull;
}

int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    
    int n = get_n();
    
    vi a, b;
    forsn(i, 3, n + 1) (is_clockwise(1, 2, i) ? b : a).pb(i);
    
    auto cmp = [&](const int &i, const int &j) {
        if (i == j) return false;
        return (bool) is_clockwise(1, i, j);
    };
    
    mySort(a, cmp);
    mySort(b, cmp);
    
    a.insert(begin(a), 1); a.pb(2);
    b.insert(begin(b), 2); b.pb(1);
    
    vi aHull = buildHull(a), bHull = buildHull(b);
    reverse(all(bHull));
    
    int ret = sz(aHull) + sz(bHull) - 2;
    
    if (ret <= 3) {
        give_answer(ret);
        return 0;
    }
    
    int i = sz(aHull) - 2, j = sz(bHull) - 2;
    
    if (!is_clockwise(aHull[i], 2, bHull[j])) {
        ret--;
        bool flag = true;
        while (flag) {
            flag = false;
            while (!is_clockwise(aHull[i], bHull[j], bHull[j - 1])) ret--, j--, flag = true;
            while (!is_clockwise(aHull[i - 1], aHull[i], bHull[j])) ret--, i--, flag = true;
        }
    }
    
    i = 1, j = 1;
    if (!is_clockwise(bHull[j], 1, aHull[i])) {
        ret--;
        bool flag = true;
        while (flag) {
            flag = false;
            while (!is_clockwise(bHull[j + 1], bHull[j], aHull[i])) ret--, j++, flag = true;
            while (!is_clockwise(bHull[j], aHull[i], aHull[i + 1])) ret--, i++, flag = true;
        }
    }
    
    give_answer(ret);
    
    return 0;
}
#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...