Submission #113699

#	Time	Username	Problem	Language	Result	Execution time	Memory
113699		RezwanArefin01	Triangles (CEOI18_tri)	C++17	100 / 100	29 ms	2556 KiB

tri

#include <bits/stdc++.h>
using namespace std;

#ifndef LOCAL
#include "trilib.h"
#else

const int N = 40010;

int _n;
long long x[N], y[N]; 

int get_n() {
    cin >> _n; 
    for(int i = 1; i <= _n; ++i) {
        cin >> x[i] >> y[i];
    }
    return _n;
}

int is_clockwise(int a, int b, int c) {
    assert(1 <= a && a <= _n && 1 <= b && b <= _n && 1 <= c && c <= _n && a != b && b != c && c != a); 
    return (x[b] - x[a]) * (y[c] - y[a]) - (y[b] -y[a]) * (x[c] - x[a]) < 0;
}

void give_answer(int s) {
    cout << s << endl; 
    exit(0);
}
#endif


vector<int> convex(vector<int> p) {
    sort(p.begin() + 1, p.end(), [](int i, int j) { 
        return !is_clockwise(1, i, j); 
    });
    vector<int> hull = { p[0] }; 
    for(int i = 1; i < p.size(); ++i) {
        int sz = hull.size(); 
        while(sz > 1 && is_clockwise(hull[sz - 2], hull[sz - 1], p[i])) 
            hull.pop_back(), --sz; 
        hull.push_back(p[i]); 
    }
    return hull;
}

vector<int> hull[2]; 

void fix_back() {
    hull[1].pop_back();
    while(1) {
        int sz = hull[0].size(), found = 0; 
        if(sz > 1 && is_clockwise(hull[0][sz - 2], hull[0].back(), hull[1].back())) {
            hull[0].pop_back(); 
            found = 1; 
        }
        sz = hull[1].size(); 
        if(sz > 1 && is_clockwise(hull[0].back(), hull[1].back(), hull[1][sz - 2])) {
            hull[1].pop_back(); 
            found = 1; 
        }
        if(!found) return; 
    }
}

int main(int argc, char const *argv[]) {
#ifdef LOCAL
    freopen("in", "r", stdin);
#endif
    int n = get_n(); 

    hull[0] = hull[1] = {1, 2}; 

    for(int i = 3; i <= n; ++i) {
        hull[!is_clockwise(1, 2, i)].push_back(i); 
    }

    hull[0] = convex(hull[0]); 
    hull[1] = convex(hull[1]); 

    hull[1].push_back(1);
    reverse(hull[1].begin(), hull[1].end()); 
    hull[1].pop_back();

    fix_back(); 
    reverse(hull[0].begin(), hull[0].end()); 
    reverse(hull[1].begin(), hull[1].end()); 
    swap(hull[0], hull[1]); 
    fix_back(); 

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

Compilation message (stderr)

tri.cpp: In function 'std::vector<int> convex(std::vector<int>)':
tri.cpp:38:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     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