제출 #400998

#제출 시각아이디문제언어결과실행 시간메모리
400998KoDTriangles (CEOI18_tri)C++17
100 / 100
28 ms2556 KiB
#include <bits/stdc++.h>
#include "trilib.h"

template <class T>
using Vec = std::vector<T>;

using ll = long long;

int main() {
    const int N = get_n();
    Vec<int> upper, lower;
    for (int i = 3; i <= N; ++i) {
        (is_clockwise(1, 2, i) ? lower : upper).push_back(i);
    }
    std::sort(upper.begin(), upper.end(), [&](const int i, const int j) {
        return !is_clockwise(1, i, j);
    });
    std::sort(lower.begin(), lower.end(), [&](const int i, const int j) {
        return !is_clockwise(1, i, j);
    });
    Vec<int> order;
    const auto add =[&](const int i) {
        while (order.size() >= 2 and is_clockwise(order[order.size() - 2], order[order.size() - 1], i)) {
            order.pop_back();
        }
        order.push_back(i);
    };
    upper.insert(upper.begin(), 2);
    upper.insert(upper.end(), 1);
    for (const auto x: upper) {
        add(x);
    }
    for (const auto x: lower) {
        add(x);       
    }
    const auto cur = order.size();
    for (const auto x: upper) {
        add(x);
    }
    for (const auto x: lower) {
        add(x);       
    }
    give_answer(order.size() - cur);
    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…