제출 #585128

#제출 시각아이디문제언어결과실행 시간메모리
585128hibikiTriangles (CEOI18_tri)C++11
0 / 100
1 ms212 KiB
#include<bits/stdc++.h>
#include<trilib.h>
using namespace std;

#define pb push_back
#define sz(x) (int)x.size()

int n;
vector<int> l, r;

int main()
{
    n = get_n();
    for(int i = 3; i <= n; i++)
    {
        if(is_clockwise(1, 2, i))
            r.pb(i);
        else
            l.pb(i);
    }
    vector<int> stk1, stk2, all, last;
    stk1.pb(1);
    stk1.pb(2);
    if(sz(r))
    {
        r.pb(1);
        for(auto idx: r)
        {
            if(sz(stk1) > 1 && !is_clockwise(stk1[sz(stk1) - 2], stk1[sz(stk1) - 1], idx))
            stk1.pop_back();
            stk1.pb(idx);
        }
    }
    stk2.pb(2);
    stk2.pb(1);
    if(sz(l))
    {
        l.pb(2);
        for(auto idx: l)
        {
            if(sz(stk2) > 1 && !is_clockwise(stk2[sz(stk2) - 2], stk2[sz(stk2) - 1], idx))
            stk2.pop_back();
            stk2.pb(idx);
        }
    }
    all.pb(2);
    for(int i = 2; i < sz(stk1) - 1; i++)
        all.pb(stk1[i]);
    all.pb(1);
    for(int i = 2; i < sz(stk2) - 1; i++)
        all.pb(stk2[i]);
    all.pb(2);
    last.pb(all[0]);
    last.pb(all[1]);
    for(int i = 2; i < sz(all); i++)
    {
        if(sz(last) > 1 && !is_clockwise(last[sz(last) - 2], last[sz(last) - 1], all[i]))
            last.pop_back();
        last.pb(all[i]);
    }
    give_answer(sz(last) - 1);
    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...