oj.uz

답안 #367071

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
367071 2021-02-16T07:04:23 Z CodePlatina Planine (COCI21_planine) C++14
0 / 110
 3 ms 748 KB 
#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 - 1; 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

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
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 748 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Incorrect 3 ms 748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 748 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Incorrect 3 ms 748 KB Output isn't correct
4 Halted 0 ms 0 KB -