Submission #367081

#	Time	Username	Problem	Language	Result	Execution time	Memory
367081		CodePlatina	Planine (COCI21_planine)	C++14	110 / 110	365 ms	32224 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tlll tuple<long long, long long, long long>
#define tiiii tuple<int, int, int, int>
#define tllll tuple<long long, long long, long long, long long>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
//#define DEBUG

using namespace std;

const long long INF = (long long)8e18;

struct Frac
{
    long long up, dn;

    Frac(void) : up(0), dn(1) {}
    Frac(long long x, long long y) : up(x), dn(y) { if(dn < 0) up = -up, dn = -dn; }

    bool operator< (const Frac &ot) const { return up * ot.dn < ot.up * dn; }
};

struct Line
{
    long long a, b;

    Frac eval(Frac x) { return Frac(a * x.up + b * x.dn, x.dn); }
    Frac cross(const Line &ot) const { return Frac(b - ot.b, ot.a - a); }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, h; cin >> n >> h;
    pii A[n]; for(auto &i : A) cin >> i.ff >> i.ss;

    int N = (n - 3) / 2;
    if(N == 0) { cout << 0; return 0; }
    pair<Frac, Frac> ran[N];

    vector<Line> ln;
    for(int i = 1; i < n - 1; ++i)
    {
        if(i & 1)
        {
            Line x{A[i].ff, A[i].ss};
            while(ln.size() >= 2 && x.cross(ln.back()) < x.cross(ln[(int)ln.size() - 2])) ln.pop_back();
            ln.push_back(x);
        }

        else
        {
            Line x{A[i].ff, A[i].ss};
            int s = 0, e = (int)ln.size();
            while(s + 1 < e)
            {
                int mid = s + e >> 1;
                Frac cr = ln[mid].cross(ln[mid - 1]);
                if(x.eval(cr) < ln[mid].eval(cr)) s = mid;
                else e = mid;
            }
            Frac tmp = x.cross(ln[s]);
            ran[i / 2 - 1].ff = Frac(A[i].ff * tmp.up - (h - A[i].ss) * tmp.dn, tmp.up);
        }
    }

    ln.clear();
    for(int i = n - 2; i >= 1; --i)
    {
        if(i & 1)
        {
            Line x{-A[i].ff, A[i].ss};
            while(ln.size() >= 2 && x.cross(ln.back()) < x.cross(ln[(int)ln.size() - 2])) ln.pop_back();
            ln.push_back(x);
        }

        else
        {
            Line x{-A[i].ff, A[i].ss};
            int s = 0, e = (int)ln.size();
            while(s + 1 < e)
            {
                int mid = s + e >> 1;
                Frac cr = ln[mid].cross(ln[mid - 1]);
                if(x.eval(cr) < ln[mid].eval(cr)) s = mid;
                else e = mid;
            }
            Frac tmp = x.cross(ln[s]);
            ran[i / 2 - 1].ss = Frac(A[i].ff * tmp.up + (h - A[i].ss) * tmp.dn, tmp.up);
        }
    }

    #ifdef DEBUG
        cout << endl;
        cout << "ran" << endl;
        for(int i = 0; i < N; ++i)
        {
            cout << "{ " << ran[i].ff.up << " / " << ran[i].ff.dn << " }, ";
            cout << "{ " << ran[i].ss.up << " / " << ran[i].ss.dn << " }\n";
        }
        cout << endl;
    #endif

    using pff = pair<Frac, Frac>;

    sort(ran, ran + N, [](pff x, pff y){ return x.ss < y.ss; });

    int ans = 1; Frac mn = ran[0].ss;
    for(int i = 1; i < N; ++i)
    {
        if(mn < ran[i].ff)
            ++ans, mn = ran[i].ss;
    }
    cout << ans;

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:70:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |                 int mid = s + e >> 1;
      |                           ~~^~~
Main.cpp:96:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |                 int mid = s + e >> 1;
      |                           ~~^~~

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