Submission #604757

#	Time	Username	Problem	Language	Result	Execution time	Memory
604757		pakhomovee	Triangles (CEOI18_tri)	C++17	0 / 100	1 ms	212 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);*/

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

bool lower_cmp(int i, int j) {
    return is_clockwise(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;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n = get_n();
    vector<int> upper, lower;
    for (int i = 2; i < n; ++i) {
        if (is_clockwise(1, 2, i + 1)) {
            lower.push_back(i);
        } else {
            upper.push_back(i);
        }
    }
    upper.insert(upper.begin(), 1);
    upper.push_back(0);
    sort(upper.begin() + 1, upper.begin() + upper.size() - 1, upper_cmp);
    lower.insert(lower.begin(), 1);
    lower.push_back(0);
    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) {
        give_answer(lower_hull.size());
        return 0;
    }
    reverse(lower_hull.begin(), lower_hull.end());
    for (int i : lower_hull) {
        upper_hull.push_back(i);
    }
    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);
    }
    give_answer(hull.size() - 1);
    return 0;
}

Compilation message (stderr)

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

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