이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define ld long double
#define P complex<ld>
#define X real()
#define Y imag()
int main() {
cin.sync_with_stdio(false);
cin.tie(nullptr);
int n, h;
cin >> n >> h;
vector<P> mount(n), ch;
for(auto &i: mount) {
ld a, b;
cin >> a >> b;
i={a,b};
}
vector<pair<ld,ld>> a(n,{-1e18,-1e18});
for(int i = 1; i < n-1; i++) {
while(ch.size()>1&&((mount[i]-ch.back())*conj(ch.back()-ch[ch.size()-2])).Y>=0)
ch.pop_back();
if(~i&1) {
P p = mount[i]-ch.back();
a[i].first=mount[i].X+(p.X/p.Y*(h-mount[i].Y));
}
ch.push_back(mount[i]);
}
ch.clear();
for(int i = n-1; --i;) {
while(ch.size()>1&&((mount[i]-ch.back())*conj(ch.back()-ch[ch.size()-2])).Y<=0)
ch.pop_back();
if(~i&1) {
P p = ch.back()-mount[i];
a[i].second=mount[i].X+(p.X/p.Y*(h-mount[i].Y));
}
ch.push_back(mount[i]);
}
vector<pair<ld,ld>> v;
for(auto i: a)
if(i.first!=-1e18)
v.push_back(i);
sort(v.begin(),v.end());
int ans = 0;
ld x = -1e18;
for(auto i: v) {
if(i.first-x>1e-10)
ans++,x=i.second;
else x=min(x,i.second);
}
cout << ans << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |