제출 #1360229

#제출 시각아이디문제언어결과실행 시간메모리
1360229GrayTriangles (CEOI18_tri)C++20
100 / 100
11 ms1800 KiB
#include "trilib.h"
#include <algorithm>
#include <bits/stdc++.h>

using namespace std;
#define ll int
#define ff first
#define ss second
#define ln "\n"
const ll INF = 2e9;


void solve(){
    ll n = get_n();
    vector<ll> perm;
    for (ll i=1; i<=n; i++){
        perm.push_back(i);
    }
    ll x = perm[0], y = perm[1];
    vector<ll> left, right;
    for (ll i=2; i<n; i++){
        if (is_clockwise(x, y, perm[i])) right.push_back(perm[i]);
        else left.push_back(perm[i]);
    }
    sort(right.begin(), right.end(), [&](ll i1, ll i2){
        if (i1==i2) return 0;
        return is_clockwise(x, i1, i2);
    });
    sort(left.begin(), left.end(), [&](ll i1, ll i2){
        if (i1==i2) return 0;
        return is_clockwise(x, i1, i2);
    });
    vector<ll> ord;
    for (auto z:left) ord.push_back(z);
    ord.push_back(y);
    for (auto z:right) ord.push_back(z);
    deque<ll> hull;
    hull.push_back(x);
    hull.push_back(ord[0]);
    for (ll i=1; i<n-1; i++){
        while (hull.size()>1 and !is_clockwise(hull[hull.size()-2], hull[hull.size()-1], ord[i])) hull.pop_back();
        hull.push_back(ord[i]);
    }

    while (hull.size()>3){
        if (!is_clockwise(hull.back(), hull[0], hull[1])){
            hull.pop_front();
        }else if (!is_clockwise(hull[hull.size()-2], hull.back(), hull[0])){
            hull.pop_back();
        }else break;
    }
    give_answer(hull.size());
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); ll t=1;
    // cin >> t;
    while (t--) solve();
}
#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...