Submission #604807

#	Time	Username	Problem	Language	Result	Execution time	Memory
604807		pakhomovee	Triangles (CEOI18_tri)	C++17	20 / 100	2 ms	340 KiB

tri

#include "trilib.h"
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <cassert>
#include <cstring>

using namespace std;

/*int get_n();
bool is_clockwise(int a, int b, int c);
void give_answer(int s);*/

int pi, pj;

bool upper_cmp(int i, int j) {
    return !is_clockwise(pj + 1, i + 1, j + 1);
}

bool lower_cmp(int i, int j) {
    return is_clockwise(pj + 1, i + 1, j + 1);
}

vector<int> hull_upper(vector<int> sorted_points) {
    vector<int> hull;
    for (int i : sorted_points) {
        while (hull.size() > 1 && is_clockwise(hull[hull.size() - 2] + 1, hull.back() + 1, i + 1)) hull.pop_back();
        hull.push_back(i);
    }
    return hull;
}

vector<int> hull_lower(vector<int> sorted_points) {
    vector<int> hull;
    for (int i : sorted_points) {
        while (hull.size() > 1 && !is_clockwise(hull[hull.size() - 2] + 1, hull.back() + 1, i + 1)) hull.pop_back();
        hull.push_back(i);
    }
    return hull;
}

int work() {
    int n = get_n();
    vector<int> upper, lower;
    for (int i = 2; i < n; ++i) {
        if (is_clockwise(pi + 1, pj + 1, i + 1)) {
            lower.push_back(i);
        } else {
            upper.push_back(i);
        }
    }
    upper.insert(upper.begin(), pj);
    upper.push_back(pi);
    sort(upper.begin() + 1, upper.begin() + upper.size() - 1, upper_cmp);
    lower.insert(lower.begin(), pj);
    lower.push_back(pi);
    sort(lower.begin() + 1, lower.begin() + lower.size() - 1, lower_cmp);
    vector<int> upper_hull = hull_upper(upper);
    vector<int> lower_hull = hull_lower(lower);
    if (upper_hull.size() == 2) {
        return lower_hull.size();
    }
    reverse(lower_hull.begin(), lower_hull.end());
    for (int i : lower_hull) {
        upper_hull.push_back(i);
    }
    cerr << "cand: " << upper_hull.size() << endl;
    for (int i : upper_hull) cerr << i << ' ';
    cerr << endl;
    vector<int> hull;
    for (int s = 0; s <= upper_hull.size(); ++s) {
        int i = upper_hull[(1 + s) % upper_hull.size()];
        if (!hull.empty() && i == hull.back()) continue;
        while (hull.size() > 1 && is_clockwise(hull[hull.size() - 2] + 1, hull.back() + 1, i + 1)) hull.pop_back();
        hull.push_back(i);
    }
    cerr << "res: ";
    for (int i : hull) {
        cerr << i << ' ';
    }
    cerr << endl;
    return hull.size() - 1;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    pi = 0, pj = 1;
    int ans = work();
    swap(pi, pj);
    cerr << ans << endl;
    ans = min(ans, work());
    cerr << work() << endl;
    give_answer(ans);
}

Compilation message (stderr)

tri.cpp: In function 'int work()':
tri.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (int s = 0; s <= upper_hull.size(); ++s) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~

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