# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
538973 | jamielim | Planine (COCI21_planine) | C++14 | 3 ms | 596 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;
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;
const int maxn=1000005;
int n,h;
int x[maxn],y[maxn];
double le[maxn];
pair<double,double> range[maxn]; // right, left
int num=0;
struct ch{
vector<ii> v;
void add(int i){ // add the point of index i
while(SZ(v)>=2){
ii a=v[SZ(v)-2],b=mp(x[i],y[i]);
double m=(double)(b.se-a.se)/(double)(b.fi-a.fi);
double c=(double)b.se-m*(double)(b.fi);
if(v.back().se<EPS+m*(double)(v.back().fi)+c)v.pop_back();
else break;
}
v.pb(x[i],y[i]);
}
double qry(){ // intersection of the most recent line with y=h
if(SZ(v)<2)return INF;
ii a=v[SZ(v)-2],b=v.back();
double m=(double)(b.se-a.se)/(double)(b.fi-a.fi);
double c=(double)b.se-m*(double)(b.fi);
return ((double)(h)-c)/m;
}
}fwd,bwd;
int main(){
scanf("%d%d",&n,&h);
for(int i=0;i<n;i++){
scanf("%d%d",&x[i],&y[i]);
}
for(int i=0;i<n-1;i++){
fwd.add(i);
if(i%2==0&&i>0)le[i]=fwd.qry();
}
for(int i=n-1;i>0;i--){
bwd.add(i);
if(i%2==0&&i<n-1){
range[num++]=mp(fwd.qry(),le[i]);
}
}
sort(range,range+num);
double prv=-INF;
int ctr=0;
for(int i=0;i<num;i++){
if(prv+EPS>=range[i].se){
continue;
}
prv=range[i].fi;
ctr++;
}
printf("%d",ctr);
}
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... |