제출 #656088

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
656088		andrei_marciuc	Triangles (CEOI18_tri)	C++11	100 / 100	20 ms	2260 KiB

tri

#include <algorithm>
#include <iostream>
#include <vector>
#include "trilib.h"
using namespace std;

vector<int> componenta[ 2 ];
vector<int> divide[ 2 ];
int n;

inline bool cmp( const int& a, const int& b ) {
    return ( a == b ? false : is_clockwise( 1, a, b ) );
}

int main() 
{
 
    n = get_n();
    for( int i = 0; i < 2; i++ )
        divide[ i ].push_back( 2 );
    for( int i = 3; i <= n; i++ )
        divide[ is_clockwise( 1, 2, i ) ].push_back( i );
    
    for( int comp = 0; comp < 2; comp++ ) {
        sort( divide[ comp ].begin(), divide[ comp ].end(), cmp );
        for( vector<int>::iterator it = divide[ comp ].begin(); it != divide[ comp ].end(); it++ ) {
            int right = componenta[ comp ].size();
            while( right > 1 && !is_clockwise( componenta[ comp ][ right - 2 ], componenta[ comp ].back(), *it ) ) {
                componenta[ comp ].pop_back();
                right--;
            }
            componenta[ comp ].push_back( *it );
        }
        if( comp )
            reverse( componenta[ comp ].begin(), componenta[ comp ].end() );
        componenta[ comp ].insert( componenta[ comp ].begin(), 1 );
        
    }

    /*for( int comp = 0; comp < 2; comp++ ) {
        for( int i : componenta[ comp ] )
            cout << i << ' ';
        cout << '\n';
    }*/

    if( min( componenta[ 0 ].size(), componenta[ 1 ].size() ) == 1 ) {
        give_answer( max( componenta[ 0 ].size(), componenta[ 1 ].size() ) );
        exit( 0 );
    }

    for( int comp = 0; comp < 2; comp++ ) {
        componenta[ 0 ].pop_back();

        bool good = false;
        while( !good ) {
            good = true;
            if( componenta[ 0 ].size() > 1 && !is_clockwise( componenta[ 0 ][ componenta[ 0 ].size() - 2 ], componenta[ 0 ].back(), componenta[ 1 ].back() ) ) {
                componenta[ 0 ].pop_back();
                good = false;
            }
        

            if( componenta[ 1 ].size() > 1 && !is_clockwise( componenta[ 0 ].back(), componenta[ 1 ].back(), componenta[ 1 ][ componenta[ 1 ].size() - 2 ] ) ) {
                componenta[ 1 ].pop_back();
                good = false;
            }    
        }
        reverse( componenta[ 0 ].begin(), componenta[ 0 ].end() );
        reverse( componenta[ 1 ].begin(), componenta[ 1 ].end() );
        swap( componenta[ 0 ], componenta[ 1 ] );

    }

    give_answer( componenta[ 0 ].size() + componenta[ 1 ].size() );
    return 0;
}
/*
6
1 1
4 3
2 2
1 4
5 1
3 2
*/

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