Submission #537501

#TimeUsernameProblemLanguageResultExecution timeMemory
537501joelauPlanine (COCI21_planine)C++14
30 / 110
2078 ms1908 KiB
#include <bits/stdc++.h> using namespace std; int N,H; pair<int,int> A[1000005]; vector< pair<long double,long double> > lst; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> N >> H; for (int i = 0; i < N; ++i) cin >> A[i].first >> A[i].second; for (int i = 2; i < N-1; i += 2) { long double x1 = -1e18, x2 = 1e18; for (int j = 1; j < i; j += 2) if (A[j].second > A[i].second) x1 = max(x1, A[i].first - (long double) (A[i].first - A[j].first) / (A[j].second - A[i].second) * (H - A[i].second)); for (int j = i+1; j < N; j += 2) if (A[j].second > A[i].second) x2 = min(x2, A[i].first + (long double) (A[j].first - A[i].first) / (A[j].second - A[i].second) * (H - A[i].second)); lst.emplace_back(x2,x1); } sort(lst.begin(),lst.end()); int ans = 0; long double n = -1e18; for (auto x: lst) if (n < x.second) ans++, n = x.first; cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...