Submission #467057

#TimeUsernameProblemLanguageResultExecution timeMemory
467057idk321Triangles (CEOI18_tri)C++17
0 / 100
1 ms460 KiB
#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);
    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();

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

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

                if (good) break;
            }
        }

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


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

/*
6
1 1
4 3
2 2
1 4
5 1
3 2
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...