Submission #131809

#	Time	Username	Problem	Language	Result	Execution time	Memory
131809		apostoldaniel854	Triangles (CEOI18_tri)	C++14	100 / 100	31 ms	2556 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
using namespace std;
int n;
bool cmp (int a, int b) {
    return is_clockwise (n, a, b);
}
const int N = 1e5;
int idx[1 + N];
#define pb push_back
int main () {
    n = get_n ();
    vector <int> x, y;
    for (int i = 2; i < n; i++)
        if (is_clockwise (n, i, 1))
            x.pb (i);
        else
            y.pb (i);

    sort (x.begin (), x.end (), cmp);
    sort (y.begin (), y.end (), cmp);
    int nr = 0;

    for (int it : x)
        idx[++nr] = it;

    idx[++nr] = 1;

    for (int it : y)
        idx[++nr] = it;
    vector <int> ans;
    ans.pb (n);
    ans.pb (idx[1]);
    nr = 2;

    for (int i = 2; i <= n - 1; i++) {
        while (nr >= 2 && !is_clockwise (ans[nr - 2], ans.back (), idx[i])) {
            ans.pop_back ();
            nr--;
        }

        ans.pb (idx[i]);
        nr++;
    }

    while (ans.size () > 3) {
        if (!is_clockwise(ans.back (), ans.front (), ans[1]))
            ans.erase (ans.begin ());
        else if (!is_clockwise(ans[ans.size () - 2], ans.back (), ans.front ()))
            ans.pop_back ();
        else {
            give_answer (ans.size ());
            return 0;
        }
    }
    give_answer (ans.size ());
    return 0;
}

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