#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define int long long
double n, h;
vector<pair<double, double> > arr;
vector<pair<double, double> > arr2;
pair<double, double> stackk[1000000];
bool comp(pair<double, double> i1, pair<double, double> i2){
return i1.second<i2.second;
}
signed main(){
cin >> n >> h;
if(n == 3){
cout << 0; return 0;
}
for(int i = 0; i < n; i++){
double x, y; cin >> x >> y;
if(i == 0 || i == n - 1) continue;
arr.push_back(make_pair(x, y));
}
int idx = 0;
int endpt = -1;
while(idx < (int)arr.size() - 1){
if(idx % 2){
while(endpt != -1 && stackk[endpt].second <= arr[idx].second)endpt--;
stackk[++endpt] = arr[idx];
idx++;
continue;
}
double curr = arr[idx].first - ((h - arr[idx].second) * (arr[idx].first - stackk[endpt].first)/(stackk[endpt].second - arr[idx].second));
int i = endpt-1;
while(i != -1 && curr < stackk[i].first){
curr = max(curr, arr[idx].first - ((h - arr[idx].second) * (arr[idx].first - stackk[i].first)/(stackk[i].second - arr[idx].second)));
i--;
}
arr2.push_back(make_pair(curr, 0));
idx++;
}
idx = (int)arr.size() - 1;
endpt = -1;
while(idx > 0){
if(idx % 2){
while(endpt != -1 && stackk[endpt].second <= arr[idx].second)endpt--;
stackk[++endpt] = arr[idx];
idx--;
continue;
}
double curr = arr[idx].first + ((h - stackk[endpt].second) * (stackk[endpt].first - arr[idx].first)/(arr[idx].second - stackk[endpt].second));
int i = endpt-1;
while(i != -1 && curr > stackk[i].first){
curr = min(curr, arr[idx].first + ((h - stackk[i].second) * (stackk[i].first - arr[idx].first)/(arr[idx].second - stackk[i].second)));
i--;
}
arr2[idx/2 - 1].second = curr;
idx--;
}
/*
arr[(int)arr.size() - 1].second = prex + ((h - prey) * (x - prex) / (y - prey));
arr.push_back(make_pair(x - ((h - y) * (x - prex)/(prey - y)), 0));
*/
sort(arr2.begin(), arr2.end(), comp);
int cnt = 1;
double eest = arr2[0].second;
//cout << arr[0].first << " " << arr[0].second << "\n";
for(int i = 1; i < (int)arr2.size(); i++){
//cout << arr[i].first << " " << arr[i].second << "\n";
if(arr2[i].first <= eest) continue;
eest = arr2[i].second; cnt++;
}
cout << cnt;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
