Submission #229807

#	Time	Username	Problem	Language	Result	Execution time	Memory
229807		Ruxandra985	Triangles (CEOI18_tri)	C++14	100 / 100	37 ms	2296 KiB

tri

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

int v[40010] , x[40010] , y[40010] , s[40010] , n , p[40010] , q[40010];

int cmp (int x , int y){

    return is_clockwise(n , x , y);

}
int main()
{
    FILE *fin = fopen ("a.in","r");
    FILE *fout = fopen ("a.out","w");
    int i , elem , j , bgn;
     n = get_n();

    /// stergi citirea, folosesti get_n

    for (i = 2 ; i < n ; i++){

        if (is_clockwise(n , i , 1))
            y[++y[0]] = i;
        else x[++x[0]] = i;

    }

    sort (x + 1 , x + x[0] + 1 , cmp);
    sort (y + 1 , y + y[0] + 1 , cmp);

    for (i = 1 ; i <= y[0] ; i++)
        v[i] = y[i];
    v[y[0] + 1] = 1;
    for (i = 1 ; i <= x[0] ; i++)
        v[y[0] + 1 + i] = x[i];

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

    while (elem - bgn + 1 >= 3){

        if (!is_clockwise (s[elem] , s[bgn] , s[bgn + 1])){
            bgn++;
        }
        else if (!is_clockwise (s[elem - 1] , s[elem] , s[bgn]))
            elem--;
        else break;


    }

	give_answer(max(3 , elem - bgn + 1));


    return 0;
}

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:14:11: warning: unused variable 'fin' [-Wunused-variable]
     FILE *fin = fopen ("a.in","r");
           ^~~
tri.cpp:15:11: warning: unused variable 'fout' [-Wunused-variable]
     FILE *fout = fopen ("a.out","w");
           ^~~~

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