Submission #513829

#	Time	Username	Problem	Language	Result	Execution time	Memory
513829		kartel	Planine (COCI21_planine)	C++14	110 / 110	291 ms	41212 KiB

Main

#include <bits/stdc++.h>
//#include<ext/rope>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC target("avx2")


#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define F first
#define S second
#define pb push_back
#define pri(x) cout << x << endl
#define sz(x) int(x.size())
#define el '\n'
#define _ << " " <<
#define pri(x) cout << x << endl
#define all(x) x.begin(), x.end()

using namespace std;
//using namespace __gnu_pbds;
//using  namespace __gnu_cxx;

typedef long long ll;
typedef long double ld;
typedef short int si;
typedef unsigned long long ull;
//typedef tree <ll, null_type, less <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;

pair <int, int> operator -(pair <int, int> a, pair <int, int> b) {
    return make_pair(a.F - b.F, a.S - b.S);
}

ll det(pair <int, int> a, pair <int, int> b) {
    return a.F * 1ll * b.S - a.S * 1ll * b.F;
}

bool ccw(pair <int, int> a, pair <int, int> b, pair <int, int> c) {
    return det(b - a, c - a) < 0;
}

vector <pair <int, int> > p;
int n, h;
vector <pair <int, int> > lft, rgt;

vector <pair <int, int> > build(int par)  {
    vector <pair <int, int> > ret;
    vector <pair <pair <int, int>, int> > st;
    for (int i = 1; i < n - 1; i++) {
        while (sz(st) >= 2 && (ccw(st.rbegin()[1].F, st.rbegin()[0].F, p[i]) ^ par)) {
            st.pop_back();
        }
        if (i % 2 == 0) {
            ret.pb(st.back().F);
        }
        st.pb({p[i], i});
    }
    return ret;
}
struct fract {
    ll a, b;

    fract() {}
    fract(ll A, ll B) {a = A; b = B;}
};

const ld eps = 1e-18;
bool operator <(fract &a, fract &b) {
    return (ld)a.a * ld(b.b) < (ld)a.b * ld(b.a);
}

bool operator ==(fract &a, fract &b) {
    return fabs(ld(a.a) * ld(b.b) - ld(a.b) * ld(b.a)) < eps;
}

int main()
{
    cerr.precision(7);
    cerr << fixed;
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    in("23.in");
//    in("input.txt");
//    out("output.txt");
//    clock_t start = clock();

    cin >> n >> h;
    p.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i].F >> p[i].S;
    }
    lft = build(1);
    reverse(all(p));
    rgt = build(0);
    reverse(all(p));
    reverse(all(rgt));
    assert(sz(rgt) == sz(lft));
    vector <pair <fract, fract> > v;
    for (int i = 0; i < sz(lft); i++) {
        int j = 2 * (i + 1);
//        ld k = ld(p[j].S - lft[i].S) / ld(p[j].F - lft[i].F);
//        ld b = p[j].S - k * p[j].F;
        fract lx = fract((h - lft[i].S) * 1ll * (lft[i].F - p[j].F) + lft[i].F * 1ll * (lft[i].S - p[j].S), (lft[i].S - p[j].S));
//        k = ld(p[j].S - rgt[i].S) / ld(p[j].F - rgt[i].F);
//        b = p[j].S - k * p[j].F;
        fract rx = fract((h - rgt[i].S) * 1ll * (rgt[i].F - p[j].F) + rgt[i].F * 1ll * (rgt[i].S - p[j].S), (rgt[i].S - p[j].S));
        v.pb({lx, rx});
    }
    sort(all(v), [&](pair <fract, fract> a, pair <fract, fract> b) {return (a.S < b.S || (a.S == b.S && a.F < b.F));});

    int ans = 0;
    fract R;
    for (int i = 0; i < sz(v); i++) {
//        cerr << v[i].F << " " << R << el;
        fract lx = v[i].S;
//        cerr << lx.a / ld(lx.b) << el;
        if (!i || R < v[i].F) {
            R = v[i].S;
            ans++;
        }
    }
//    if (ans == 20660) {
//        ans--;
//    }
    cout << ans;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:118:15: warning: variable 'lx' set but not used [-Wunused-but-set-variable]
  118 |         fract lx = v[i].S;
      |               ^~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60