Submission #958684

#TimeUsernameProblemLanguageResultExecution timeMemory
958684LucaIlieTriangles (CEOI18_tri)C++17
0 / 100
1 ms600 KiB
#include <bits/stdc++.h>
#include "trilib.h"

using namespace std;

int main() {
    int n = get_n();
    vector<int> up, down;

    for ( int i = 3; i <= n; i++ ) {
        if ( is_clockwise( 1, 2, i ) )
            down.push_back( i );
        else
            up.push_back( i );
    }

    sort( down.begin(), down.end(), []( int a, int b ) {
        return is_clockwise( 1, a, b );
    } );
    sort( up.begin(), up.end(), []( int a, int b ) {
        return is_clockwise( 1, a, b );
    } );

    vector<int> order;
    order.push_back( 1 );
    for ( int a: up )
        order.push_back( a );
    order.push_back( 2 );
    for ( int a: down )
        order.push_back( a );

    vector<int> stack;
    stack.push_back( order[0] );
    stack.push_back( order[1] );
    for ( int i = 2; i < n; i++ ) {
        while ( stack.size() >= 2 && !is_clockwise( stack[stack.size() - 2], stack[stack.size() - 1], order[i] ) )
            stack.pop_back();
        stack.push_back( order[i] );
    }

    give_answer( stack.size() );

    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...