Submission #1039233

#TimeUsernameProblemLanguageResultExecution timeMemory
1039233slivajanTriangles (CEOI18_tri)C++17
55 / 100
7 ms1624 KiB
#include "trilib.h"

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

typedef long long un;
typedef vector<un> vuc;
typedef set<un> sun;

#define vec vector
#define REP(i, a, b) for (un i = (un)a; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define ALL(x) (x).begin(), (x).end()

un N;
vuc horni;
vuc dolni;
vuc cely;
vuc obal;

int main(){
    N = get_n();

    REP(i, 3, N+1){
        if (not is_clockwise(1, 2, i)) horni.push_back(i);
        else dolni.push_back(i);
    }

    horni.push_back(2);
    dolni.push_back(2);

    sort(ALL(horni), [](un x, un y){return is_clockwise(1, x, y); });
    sort(ALL(dolni), [](un x, un y){return is_clockwise(1, x, y); });

    FEAC(a, horni) cely.push_back(a);
    cely.pop_back();
    FEAC(a, dolni) cely.push_back(a);

    obal.push_back(1);
    FEAC(a, cely){
        while((obal.size() != 1) and (not is_clockwise(obal[obal.size()-2], obal[obal.size()-1], a))){
            obal.pop_back();
        }
        obal.push_back(a);
    }

    vuc obal_cp = obal;
    un num = 0;

    FEAC(a, obal_cp){
        while((obal.size() != 1) and (not is_clockwise(obal[obal.size()-2], obal[obal.size()-1], a))){
            obal.pop_back();
            num--;
        }
        obal.push_back(a);
        num++;
        if (num == 2) break;
    }

    un prvni = obal[obal.size()-2];

    un p_idx = 0;
    while(prvni != obal[p_idx]) p_idx++;

    give_answer(obal.size() - p_idx - 2);
}
#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...