# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
375271 | 2021-03-09T05:58:22 Z | Nordway | Planine (COCI21_planine) | C++14 | 0 ms | 0 KB |
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #define x first #define y second #define pb push_back #define mp make_pair #define all(v) v.begin(),v.end() #define sz(v) (int)v.size() #define up_b upper_bound #define low_b lower_bound #define nl '\n' using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set; const int N=1e6+11; const int M=1e6+1; const ll inf=1e9+11; const ld EPS=1e-6; const ll INF=1e18; const ll mod=/*999999001*/1e9+7; const int dx[4]={1,2,2,-1}; const int dy[4]={2,1,-1,2}; struct line{ ld a,b; }; line create(int xi,int yi,int xj,int yj){ ld dx=xi-xj,dy=yi-yj; line l; l.a=dy/dx; l.b=yi-l.a*xi; return l; } ld get(line l,int y){ return (y-l.b)/l.a; } int x[N],y[N]; ld l[N],r[N]; void solve(){ int n,h; cin>>n>>h; for(int i=1;i<=n;i++){ cin>>x[i]>>y[i]; } for(int i=3;i<n;i+=2){ line l1=create(x[i],y[i],x[i-1],y[i-1]); line l2=create(x[i+1],y[i+1],x[i],y[i]); l[i]=get(l1,h); r[i]=get(l2,h); /cout<<l[i]<<" "<<r[i]<<endl; } ld L=l[3],R=r[3]; int ans=1; for(int i=5;i<n;i+=2){ if(r[i]<L||l[i]>R){ ans++; L=l[i]; R=r[i]; } else{ L=max(L,l[i]); R=min(R,r[i]); } } cout<<ans; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0),cout.tie(0); int T=1; //cin>>T; for(int i=1;i<=T;i++){ solve(); cout<<nl; } return 0; }