Submission #1039930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039930		0npata	Triangles (CEOI18_tri)	C++17	100 / 100	17 ms	4284 KiB

tri

#include<bits/stdc++.h>
#include "trilib.h"

using namespace std;

#define vec vector
#define int long long

int n;

bool on_the_right(int i, int j, int k) {
    if(i==j || j == k || i == k) return false;
    return is_clockwise(i+1, j+1, k+1);
}

bool is_on_convex_hull(int i) {
    int mx = i == 0 ? 1 : 0;

    for(int j = 0; j<n; j++) {
        if(j == i || j == mx) continue;
        if(on_the_right(i, mx, j)) mx = j;
    }

    for(int j = 0; j<n; j++) {
        if(j == i || j == mx) continue;
        if(on_the_right(i, mx, j)) return false;
    }

    return true;
}

vec<int> convex_hull_from_point(int p, vec<int> all_points) {
    sort(all_points.begin(), all_points.end(), [&](int i, int j) { return on_the_right(p, j, i); });
    vec<int> stk{p};
    all_points.push_back(p);
    for(int p_nxt : all_points) {
        while(stk.size() > 1 && on_the_right(stk[stk.size()-2], stk[stk.size()-1], p_nxt)) {
            stk.pop_back();
        }
        stk.push_back(p_nxt);
    }
    stk.pop_back();
    return stk;
}

int32_t main() {
    n = get_n();
    
    int p1 = 0;
    int p2 = 1;
    vec<int> ps_r{};
    vec<int> ps_l{};
    for(int i = 2; i<n; i++) {
        if(on_the_right(p1, p2, i)) ps_r.push_back(i);
        else ps_l.push_back(i);
    }

    vec<int> ch_l = convex_hull_from_point(p1, ps_l);
    vec<int> ch_r = convex_hull_from_point(p2, ps_r);


    int l_i = 0;
    int r_i = 0;

    vec<int> chnxt(n, -1);
    for(int i = 0; i<ch_l.size(); i++) {
        chnxt[ch_l[i]] = ch_l[(i+1)%ch_l.size()];
    }
    for(int i = 0; i<ch_r.size(); i++) {
        chnxt[ch_r[i]] = ch_r[(i+1)%ch_r.size()];
    }


    while(1) {
           int l_i_nxt = (l_i+1)%ch_l.size();
           int r_i_nxt = (r_i-1+ch_r.size())%ch_r.size();
           if(on_the_right(ch_r[r_i], ch_l[l_i], ch_l[l_i_nxt])) {
               l_i = l_i_nxt;
               continue;
           }
           if(on_the_right(ch_r[r_i], ch_l[l_i], ch_r[r_i_nxt])) {
               r_i = r_i_nxt;
               continue;
           }
           chnxt[ch_r[r_i]] = ch_l[l_i];
           break;
    }
    l_i = 0;
    r_i = 0;

    while(1) {
           int l_i_nxt = (l_i-1+ch_l.size())%ch_l.size();
           int r_i_nxt = (r_i+1)%ch_r.size();
           if(on_the_right(ch_l[l_i], ch_r[r_i], ch_l[l_i_nxt])) {
               l_i = l_i_nxt;
               continue;
           }
           if(on_the_right(ch_l[l_i], ch_r[r_i], ch_r[r_i_nxt])) {
               r_i = r_i_nxt;
               continue;
           }
           chnxt[ch_l[l_i]] = ch_r[r_i];
           break;
    }
    
    
    vec<int> ch{ch_l[0]};
    for(int i = 0; i<n*2; i++) {
        ch.push_back(chnxt[ch.back()]);
    }
    reverse(ch.begin(), ch.end());
    vec<bool> used(n);
    int ans = 0;
    for(int p : ch) {
        if(used[p]) break;
        used[p] = true;
        ans++;
    }

    give_answer(ans);

    return 0;
}

Compilation message (stderr)

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

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