Submission #467059

#	Time	Username	Problem	Language	Result	Execution time	Memory
467059		idk321	Triangles (CEOI18_tri)	C++17	100 / 100	26 ms	2316 KiB

tri

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

const int N = 501;
int n;

vector<int> divide[2];
vector<int> hull[2];

bool comp(int a, int b) {
    if (a == b) return false;
    return is_clockwise(1, a, b);
}

bool call_is_clockwise(int a, int b, int c) {
    bool res = is_clockwise(a, b, c);
    //cout << a << " " << b << " " << c << " " << res << endl;
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    n = get_n();
    for (int i = 0; i < 2; i++) divide[i].push_back(2);
    for (int i = 3; i <= n; i++) {
        divide[is_clockwise(1, 2, i)].push_back(i);
    }

    for (int tp = 0; tp < 2; tp++) {

        sort(divide[tp].begin(), divide[tp].end(), comp);
        for (int i : divide[tp]) {
            int r = hull[tp].size();
            while (r > 1 && !call_is_clockwise(hull[tp][r - 2], hull[tp][r - 1], i)) {
                r--;
                hull[tp].pop_back();
            }
            hull[tp].push_back(i);
        }

        if (tp) reverse(hull[tp].begin(), hull[tp].end());
        hull[tp].insert(hull[tp].begin(), 1);
    }

    if (min(hull[0].size(), hull[1].size()) == 1)
    {
        give_answer(max(hull[0].size(), hull[1].size()));
        return 0;
    }

    /*
    for (int i : hull[0]) cout << i << " ";
    cout << endl;
    for (int i : hull[1]) cout << i << " ";
    cout << endl; */
    for (int i = 0; i < 2; i++) {
        hull[0].pop_back();


        while (true) {
            bool good = true;
            if (hull[0].size() > 1 && !call_is_clockwise(hull[0][hull[0].size() - 2], hull[0][hull[0].size() - 1], hull[1].back())) {
                good = false;
                hull[0].pop_back();
            }

            if (hull[1].size() > 1 && !call_is_clockwise(hull[0].back(), hull[1][hull[1].size() - 1], hull[1][hull[1].size() - 2])) {
                good = false;
                hull[1].pop_back();
            }

            if (good) break;
        }


        for (int tp = 0; tp < 2; tp ++) reverse(hull[tp].begin(), hull[tp].end());
        swap(hull[0], hull[1]);
    }


    give_answer(hull[0].size() + hull[1].size());
}

/*
6
1 1
4 3
2 2
1 4
5 1
3 2
*/

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