Submission #229756

#	Time	Username	Problem	Language	Result	Execution time	Memory
229756		Ruxandra985	Triangles (CEOI18_tri)	C++14	0 / 100	5 ms	512 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
using namespace std;
 
int v[40010] , x[40010] , y[40010] , s[40010];
 
 
int poz (int st,int dr){
    int ds=0,dd=-1,aux;
    while (st!=dr){
        if (is_clockwise(1 , st , dr)){
            aux=v[st];
            v[st]=v[dr];
            v[dr]=aux;
            aux=ds;
            ds=-dd;
            dd=-aux;
        }
        st+=ds;
        dr+=dd;
    }
    return st;
}
void sorteaza (int st,int dr){
    if (st<dr){
        int pivr = ((long long)rand()*rand())%(dr-st+1)+st;
        int p = poz(st , pivr);
        p = poz(p , dr);
        sorteaza (st , p-1);
        sorteaza (p+1 , dr);
    }
}
 
int main()
{
    int n , i , elem , j;
    n = get_n();
 
    /// stergi citirea, folosesti get_n
 
    for (i = 1 ; i <= n ; i++)
        v[i] = i;
 
    sorteaza (2 , n);
 
    /*for (i = 1 ; i <= n ; i++){
        fprintf (fout,"%d\n" , v[i]);
    }*/
 
    v[n + 1] = 1;
    s[1] = v[1];
    s[2] = v[2];
    elem = 2;
    for (j = 3 ; j <= n + 1 ; j++){
        while (elem >= 2 && is_clockwise (s[elem - 1] , s[elem] , v[j]))
            elem--;
      	if (j != n + 1)
        	s[++elem] = v[j];
    }
    elem = max(elem , 3);
 
    give_answer(elem);
 
 
    return 0;
}

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