Submission #1297970

#TimeUsernameProblemLanguageResultExecution timeMemory
1297970HiepVu217Planine (COCI21_planine)C++20
110 / 110
233 ms63960 KiB
//Proud of You//
#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
const int N = 1e6 + 17;
int n, H;
struct Vector
{
    long long x, y;
    Vector operator - (const Vector& other) const
    {
        return {x - other.x, y - other.y};
    }
    long long operator * (const Vector& other) const
    {
        return x * other.y - y * other.x;
    }
} P[N];
long long CCW(const Vector& A, const Vector& B, const Vector& C) {
    return ((B - A) * (C - A));
}
long double getintersect(const Vector& A, const Vector& B)
{
    return A.x - 1.0L * (A.x - B.x) / (A.y - B.y) * (A.y - H);
}
long double L[N], R[N];
vector <Vector> CH;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> H;
    for (int i = 1; i <= n; ++i)
    {
        cin >> P[i].x >> P[i].y;
    }
    for (int i = 2; i <= n; ++i)
    {
        while (CH.size() >= 2 && CCW (*----CH.end(), CH.back(), P[i]) >= 0)
        {
            CH.pop_back();
        }
        CH.push_back (P[i]);
        if (i % 2 == 1)
        {
            L[i] = getintersect (CH.back(), *----CH.end());
        }
    }
    CH.clear();
    for (int i = n - 1; i >= 1; --i)
    {
        while (CH.size() >= 2 && CCW (*----CH.end(), CH.back(), P[i]) <= 0)
        {
            CH.pop_back();
        }
        CH.push_back(P[i]);
        if (i % 2 == 1)
        {
            R[i] = getintersect (CH.back(), *----CH.end());
        }
    }
    int ans = 0;
    vector <pair <long double, long double>> range;
    for (int i = 3; i <= n - 2; i += 2)
    {
        range.push_back ({L[i], R[i]});
    }
    sort (range.begin(), range.end());
    for (int i = 0; i < range.size();)
    {
        int j = i;
        long double to = 1e9;
        while (j < range.size() && range[j].first <= to)
        {
            to = min(to, range[j].second), ++j;
        }
        ++ans;
        i = j;
    }
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...