Submission #539096

#TimeUsernameProblemLanguageResultExecution timeMemory
539096aniervsTriangles (CEOI18_tri)C++17
0 / 100
1 ms212 KiB
#include<bits/stdc++.h>
#include "trilib.h"
#define endl '\n' 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;

using ll = long long;
using db = long double;
const int maxn = 2e5 + 5;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

vector<int> arr[2];

void merge_sort(vector<int> &a, int l, int r){
    if(l >= r){
        return;
    }
    int mid = (l + r)>>1;
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);
    vector<int> c;
    merge(a.begin() + l, a.begin() + mid + 1, a.begin() + mid + 1, a.begin() + r + 1, back_inserter(c),  [&a](const int p, const int q){
        return !is_clockwise(a[0], p, q);
    });
    for(int i = l, j = 0; i <= r; i++, j++){
        a[i] = c[j];
    }
}

vector<int> compute_convex_hull(vector<int> a){
    if(a.size() <= 2)
        return a;
    merge_sort(a, 1, a.size() - 1);
    vector<int> h;

    for(auto p:a){
        while(h.size() > 1 and is_clockwise(h[h.size() - 2], h[h.size() - 1], p))
            h.pop_back();
        h.push_back(p);
    }

    return h;
}

vector<int> merge_convex(const vector<int> &a, const vector<int> &b){
    int n = a.size(), m = b.size();
    if(n <= 2) return b;
    if(m <= 2) return a;

    int l1, l2, r1, r2;

    vector<int> c;
    {
        // upper part
        int l = 0, r = 0;
        while(true){
            if(!is_clockwise(a[l], b[r], b[(r - 1 + m) % m])) r = (r - 1 + m) % m;
            else if(is_clockwise(b[r], a[l], a[(l + 1)% n])) l = (l + 1) % n;
            else break;
        }

        l1 = l, r1 = r;
        
    }
    
    {
        // lower part
        int l = 0, r = 0;
        while(true){
            if(is_clockwise(a[l], b[r], b[(r + 1) % m])) r = (r + 1) % m;
            else if(!is_clockwise(b[r], a[l], a[(l - 1 + n) % n])) l = (l - 1) % n;
            else break;
        }

        l2 = l, r2 = r;
    }  
    while(true){
        c.push_back(a[l1]);
        if(l1 == l2) break;
        l1 = (l1 + 1) % n;
    }
    while(true){
        c.push_back(b[r2]);
        if(r2 == r1) break;
        r2 = (r2 + 1) % n; 
    }
    
    sort(all(c));
    c.erase(unique(all(c)), c.end());

    return c;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout.setf(ios::fixed); cout.precision(0); 

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

    arr[0] = compute_convex_hull(arr[0]);
    arr[1] = compute_convex_hull(arr[1]);
    
    auto ans = merge_convex(arr[0], arr[1]);

    give_answer(ans.size());

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...