제출 #1350101

#제출 시각아이디문제언어결과실행 시간메모리
1350101biankTriangles (CEOI18_tri)C++20
100 / 100
10 ms1652 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

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);
    };
    
    sort(all(a), cmp);
    sort(all(b), cmp);
    
    a.insert(begin(a), 1); a.pb(2);
    b.insert(begin(b), 2); b.pb(1);
    
    vi aHull, bHull;
    for (int i : a) {
        while (sz(aHull) >= 2 && !is_clockwise(end(aHull)[-2], end(aHull)[-1], i)) aHull.pop_back();
        aHull.pb(i);
    }
    for (int i : b) {
        while (sz(bHull) >= 2 && !is_clockwise(end(bHull)[-2], end(bHull)[-1], i)) bHull.pop_back();
        bHull.pb(i);
    }
    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...