| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 229753 | Ruxandra985 | Triangles (CEOI18_tri) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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--;
s[++elem] = v[j];
}
if (n >= 3)
elem = max(elem , 4LL);
give_answer(elem - 1);
return 0;
}