제출 #898593

#제출 시각아이디문제언어결과실행 시간메모리
898593vjudge1Planine (COCI21_planine)C++17
110 / 110
498 ms94468 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...