Submission #604869

#	Time	Username	Problem	Language	Result	Execution time	Memory
604869		pakhomovee	Triangles (CEOI18_tri)	C++17	100 / 100	181 ms	3140 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) {
    if (i == j) return false;
    return !is_clockwise(2, i + 1, j + 1);
}
 
bool lower_cmp(int i, int j) {
    if (i == j) return false;
    return is_clockwise(2, 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);
        }
    }
    sort(upper.begin(), upper.end(), upper_cmp);
    upper.insert(upper.begin(), 1);
    upper.push_back(0);
    sort(lower.begin(), lower.end(), lower_cmp);
    lower.insert(lower.begin(), 1);
    lower.push_back(0);
    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);
    }
    cerr << "candidates: ";
    for (int i : upper_hull) {
        cerr << i << ' ';
    }
    cerr << endl;
    vector<int> hull;
    vector<bool> in(n, true);
    for (int s = 0; s < upper_hull.size() * 2; ++s) {
        int i = upper_hull[(1 + s) % upper_hull.size()];
        if (!hull.empty() && i == upper_hull[(s) % upper_hull.size()]) continue;
        while (hull.size() > 1 && is_clockwise(hull[hull.size() - 2] + 1, hull.back() + 1, i + 1)) {
            in[hull.back()] = false;
            hull.pop_back();
        }
        hull.push_back(i);
    }
    int ans = 0;
    for (int i : hull) {
        if (in[i]) {
            ++ans;
            in[i] = false;
        }
    }
    give_answer(ans);
    return 0;
}

Compilation message (stderr)

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

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