제출 #229777

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
229777		Ruxandra985	Triangles (CEOI18_tri)	C++14	20 / 100	5 ms	384 KiB

tri

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

long long v[40010] , x[40010] , y[40010] , s[40010];

int cmp (int x , int y){

    return !is_clockwise(1 , x , y);

}
int main()
{
    long long n , i , elem , j , aux , sol;
    n = get_n();

    /// stergi citirea, folosesti get_n

    for (i = 1 ; i <= n ; i++)
        v[i] = i;

    sort (v + 2 , v + n + 1 , cmp);

    /*for (i = 1 ; i <= n ; i++){
        fprintf (fout,"%d\n" , v[i]);
    }*/
    sol = 3;

    for (i = 1 ; i <= n ; i++){
        s[1] = v[1];
        s[2] = v[2];
        elem = 2;
        for (j = 3 ; j <= n ; j++){
            while (elem >= 2 && is_clockwise (s[elem - 1] , s[elem] , v[j]))
                elem--;
            s[++elem] = v[j];
        }


        while (elem >= 2 && is_clockwise (s[elem - 1] , s[elem] , s[1]))
            elem--;

        while (elem >= 2 && is_clockwise (s[elem] , s[1] , s[2]))
            elem--;

        sol = max(sol , elem);


        aux = v[1];

        for (j = 2 ; j <= n ; j++)
            v[j - 1] = v[j];

        v[n] = aux;


    }

    give_answer((int)sol);


    return 0;
}

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