Submission #958684

#	Time	Username	Problem	Language	Result	Execution time	Memory
958684		LucaIlie	Triangles (CEOI18_tri)	C++17	0 / 100	1 ms	600 KiB

tri

#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;
}

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