# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
541368 | AlperenT | Planine (COCI21_planine) | C++17 | 3 ms | 980 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, h, ans;
pair<long long, long long> arr[N];
vector<pair<long double, long double>> v;
long double l, r, mn;
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin >> n >> h;
for(int i = 1; i <= n; i++) cin >> arr[i].first >> arr[i].second;
for(int i = 3; i <= n - 2; i += 2){
l = arr[i].first - ((long double)h / (arr[i - 1].second - arr[i].second)) * (arr[i].first - arr[i - 1].first);
r = arr[i].first + ((long double)h / (arr[i + 1].second - arr[i].second)) * (arr[i + 1].first - arr[i].first);
v.push_back({l, r});
}
sort(v.begin(), v.end());
mn = v[0].second;
for(int i = 1; i < v.size(); i++){
if(mn < v[i].first){
ans++;
mn = v[i].second;
}
else mn = min(mn, v[i].second);
}
cout << ans + 1;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |