Submission #973852

#	Time	Username	Problem	Language	Result	Execution time	Memory
973852		efedmrlr	Triangles (CEOI18_tri)	C++17	100 / 100	20 ms	3028 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
#define lli long long int
#define ld long double
#define pb push_back
#define MP make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

int n;
void find_hull(vector<int> &p, vector<int> &hull) {
    if(p.size() < 3) return;
    int piv = p[0];
    p.erase(p.begin());
    auto comp = [&piv](int x, int y) {
        return is_clockwise(piv, x, y);
    };
    sort(all(p), comp);
    hull.clear();
    hull.pb(piv);
    hull.pb(p[0]);
    for(int i = 1; i < p.size(); i++) {
        while(hull.size() > 1 && !is_clockwise(hull[hull.size() - 2], hull.back(), p[i])) {
            hull.pop_back();
        } 
        hull.pb(p[i]);
    }

}

void solve() {
    n = get_n();
    vector<int> p;
    for(int i = 1; i <= n; i++) {
        p.pb(i);
    }
    vector<int> pl = {2, 1}, pr = {1, 2};
    for(int i = 3; i <= n; i++) {
        if(is_clockwise(1, 2, i)) {
            pl.pb(i);
        }
        else {
            pr.pb(i);
        }
    }
    vector<int> hull1, hull2;
    find_hull(pl, hull1);
    find_hull(pr, hull2);
    // hull1 starts with 2, hull2 starts with 1
    // cout << "hull1: ";
    // for(auto c : hull1) {
    // cout << c << " ";
    // }
    // cout << "\nhull2: ";
    // for(auto c : hull2) {
    //     cout << c << " ";
    // }
    // cout << "\n";
    if(hull1.empty()) {
        give_answer(hull2.size());
        return;
    }
    if(hull2.empty()) {
        give_answer(hull1.size());
        return;
    }
    hull1.pop_back(); hull2.pop_back();

    reverse(all(hull1));
    while(1) {
        if(hull1.size() > 1 && hull2.size() && !is_clockwise(hull2.back(), hull1.back(), hull1[hull1.size() - 2])) {
            hull1.pop_back();
            continue;
        } 
        if(hull2.size() > 1 && hull1.size() && !is_clockwise(hull2[hull2.size() - 2], hull2.back(), hull1.back())) {
            hull2.pop_back();
            continue;
        }
        break;
    }   
    reverse(all(hull1));
    reverse(all(hull2));
    while(1) {
        if(hull1.size() > 1 && hull2.size() && is_clockwise(hull2.back(), hull1.back(), hull1[hull1.size() - 2])) {
            hull1.pop_back();
            continue;
        } 
        if(hull2.size() > 1 && hull1.size() && is_clockwise(hull2[hull2.size() - 2], hull2.back(), hull1.back())) {
            hull2.pop_back();
            continue;
        }
        break;
    }   
    for(auto c : hull2) {
        hull1.pb(c);
    }
    sort(all(hull1));
    hull1.resize(unique(all(hull1)) - hull1.begin());
    give_answer(hull1.size());
}

signed main() {
    solve();
}

Compilation message (stderr)

tri.cpp: In function 'void find_hull(std::vector<int>&, std::vector<int>&)':
tri.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i = 1; i < p.size(); i++) {
      |                    ~~^~~~~~~~~~

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