Submission #538975

#	Time	Username	Problem	Language	Result	Execution time	Memory
538975		jamielim	Planine (COCI21_planine)	C++14	110 / 110	275 ms	37744 KiB

Main

#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 double EPS=1e-10;

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(bwd.qry(),le[i]);
			//printf("%f %f\n",range[num-1].fi,range[num-1].se);
		}
	}
	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)

Main.cpp: In function 'int main()':
Main.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |  scanf("%d%d",&n,&h);
      |  ~~~~~^~~~~~~~~~~~~~
Main.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%d%d",&x[i],&y[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60