Submission #329128

#	Time	Username	Problem	Language	Result	Execution time	Memory
329128		Peti	Triangles (CEOI18_tri)	C++14	100 / 100	31 ms	2540 KiB

tri

#include <iostream>
#include <algorithm>
#include <vector>
#include "trilib.h"

using namespace std;

int burok[(int)4e4], hely[(int)4e4];
int veg = 0;

int main()
{
    int n = get_n();

    vector<int> vl, vr;
    for(int i = 3; i <= n; i++){
        if(is_clockwise(1, 2, i))
            vr.push_back(i);
        else
            vl.push_back(i);
    }

    sort(vr.begin(), vr.end(), [](int a, int b) {return is_clockwise(1, b, a);});
    sort(vl.begin(), vl.end(), [](int a, int b) {return is_clockwise(1, b, a);});

    vector<int> sor(n);
    int x = 0;
    sor[x++] = 1;
    for(int y : vr)
        sor[x++] = y;
    sor[x++] = 2;
    for(int y : vl)
        sor[x++] = y;

    burok[veg++] = sor[0];
    burok[veg++] = sor[1];

    for(int i = 2; i < n; i++){
        int x = i%n;
        while(veg > 1 && is_clockwise(burok[veg-2], burok[veg-1], sor[x]))
            veg--;
        burok[veg++] = sor[x];
    }
    while(veg > 1 && is_clockwise(burok[veg-2], burok[veg-1], sor[0]))
            veg--;

    for(int i = 0; i < n; i++)
        hely[sor[i]-1] = i;

    int s = 0;
    while(hely[burok[s]-1] < hely[1])
        s++;

    s = hely[burok[s]-1];
    burok[0] = sor[s];
    burok[1] = sor[(s+1)%n];
    veg = 2;
    for(int i = s+2; i < n+s; i++){
        int x = i%n;
        while(veg > 1 && is_clockwise(burok[veg-2], burok[veg-1], sor[x]))
            veg--;
        burok[veg++] = sor[x];
    }

     while(veg > 1 && is_clockwise(burok[veg-2], burok[veg-1], sor[s]))
            veg--;

    give_answer(veg);

    return 0;
}

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