제출 #898131

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
898131		math_rabbit_1028	Triangles (CEOI18_tri)	C++14	0 / 100	1 ms	348 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
using namespace std;

int n, origin;
vector<int> arr;

bool compare(int i, int j) {
    return is_clockwise(i, origin, j);
}



void solve() {

    n = get_n();

    int k = 1, l = 2, t = 0;
    while (++t) {
        bool f = false;
        for (int i = 1; i <= n; i++) {
            if (i != k && i != l) {
                if (is_clockwise(k, l, i)) {
                    f = true;
                    if (t % 2 == 1) k = i;
                    else l = i;
                    break;
                }
            }
        }
        if (!f) break;
    }

    origin = k;

    for (int i = 1; i <= n; i++) if (i != origin) arr.push_back(i);
    sort(arr.begin(), arr.end(), compare);

    stack<int> stk;
    stk.push(origin);
    stk.push(arr[0]);
    for (int i = 1; i <= n; i++) {
        int a = stk.top(); stk.pop();
        while (stk.size() >= 2 && !is_clockwise(stk.top(), a, i)) {
            stk.top() = a; stk.pop();
        }
        stk.push(a);
        stk.push(i);
    }

    give_answer(stk.size());

}

int main() {
    solve();
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 25