oj.uz

Submission #537723

# Submission time Handle Problem Language Result Execution time Memory
537723 2022-03-15T12:30:01 Z jamezzz Planine (COCI21_planine) C++17
110 / 110
 397 ms 56992 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define INF 1023456789
typedef long long ll;
typedef long double ld;
typedef pair<ld,ld> ii;

#define maxn 1000005
 
int n,h,x[maxn],y[maxn],px[maxn],py[maxn],nx[maxn],ny[maxn];
 
struct line{
	ll x1,x2,y1,y2;
	int cross(line &o){//where does this line intersect
		ll x3=o.x1,x4=o.x2,y3=o.y1,y4=o.y2;
		if((x1-x2)*(y3-y4)==(x3-x4)*(y1-y2))return 2;//parallel
		ll num=(y3-y4)*(y1*(x1-x2)-x1*(y1-y2))-(y1-y2)*(y3*(x3-x4)-x3*(y3-y4));
		ll den=(y3-y4)*(x1-x2)-(y1-y2)*(x3-x4);
		if(num==h*den)return 0;//intersect exactly
		if((den>0&&num<h*den)||(den<0&&num>h*den))return -1;//intersect below
		if((den>0&&num>h*den)||(den<0&&num<h*den))return 1;//intersect above
	}
	bool cmp(line &o){
		ll a=x2-x1,b=y2-y1,c=o.x2-o.x1,d=o.y2-o.y1;
		if(x1<o.x1){
			if(b*c>d*a)return true;//intersect below
			if(cross(o)<=0)return false;
			else return true;
		}
		else{
			if(b*c<d*a)return false;//intersect below
			if(cross(o)==-1)return true;
			else return false;
		}
	}
};
 
struct valley{
	line l1,l2;
};

vector<valley> r;
vector<int> hull;
 
int main(){
	sf("%d%d",&n,&h);
	for(int i=1;i<=n;++i)sf("%d%d",&x[i],&y[i]);
	hull.pb(1);
	for(int i=1;i<=n;++i){
		while(sz(hull)>=2){
			int a=hull[sz(hull)-2],b=hull.back();
			int x1=x[a],y1=y[a],x2=x[b],y2=y[b],x3=x[i],y3=y[i];
			if((ll)(y2-y1)*(x3-x2)<=(ll)(y3-y2)*(x2-x1))hull.pop_back();
			else break;
		}
		int a=hull.back();
		px[i]=x[a],py[i]=y[a];
		hull.push_back(i);
	}
	while(!hull.empty())hull.pop_back();
	hull.pb(n);
	for(int i=n;i>=1;--i){
		while(sz(hull)>=2){
			int a=hull[sz(hull)-2],b=hull.back();
			int x1=x[a],y1=y[a],x2=x[b],y2=y[b],x3=x[i],y3=y[i];
			if((ll)(y1-y2)*(x2-x3)>=(ll)(y2-y3)*(x1-x2))hull.pop_back();
			else break;
		}
		int a=hull.back();
		nx[i]=x[a],ny[i]=y[a];
		hull.push_back(i);
	}
	for(int i=3;i<n;i+=2){
		line l1={x[i],px[i],y[i],py[i]};
		line l2={x[i],nx[i],y[i],ny[i]};
		r.pb({l1,l2});
	}
	sort(all(r),[](valley &a,valley &b){
		return a.l2.cmp(b.l2);
	});
	int ans=0;
	line pv=r[0].l1;
	pv.x1-=1;pv.x2-=1;
	for(int i=0;i<sz(r);++i){
		if(pv.cross(r[i].l1)>=1){
			++ans;pv=r[i].l2;
		}
	}
	pf("%d\n",ans);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:54:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |  sf("%d%d",&n,&h);
      |    ^
Main.cpp:55:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |  for(int i=1;i<=n;++i)sf("%d%d",&x[i],&y[i]);
      |                         ^
Main.cpp: In member function 'int line::cross(line&)':
Main.cpp:30:2: warning: control reaches end of non-void function [-Wreturn-type]
   30 |  }
      |  ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1232 KB Output is correct
2 Correct 6 ms 1232 KB Output is correct
3 Correct 6 ms 1244 KB Output is correct
4 Correct 34 ms 6972 KB Output is correct
5 Correct 32 ms 6956 KB Output is correct
6 Correct 32 ms 6948 KB Output is correct
7 Correct 301 ms 56852 KB Output is correct
8 Correct 334 ms 56800 KB Output is correct
9 Correct 348 ms 56804 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1232 KB Output is correct
2 Correct 6 ms 1232 KB Output is correct
3 Correct 6 ms 1244 KB Output is correct
4 Correct 34 ms 6972 KB Output is correct
5 Correct 32 ms 6956 KB Output is correct
6 Correct 32 ms 6948 KB Output is correct
7 Correct 301 ms 56852 KB Output is correct
8 Correct 334 ms 56800 KB Output is correct
9 Correct 348 ms 56804 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 314 ms 56860 KB Output is correct
18 Correct 320 ms 56992 KB Output is correct
19 Correct 33 ms 6984 KB Output is correct
20 Correct 328 ms 56724 KB Output is correct
21 Correct 32 ms 6884 KB Output is correct
22 Correct 364 ms 56864 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 322 ms 56876 KB Output is correct
25 Correct 28 ms 6968 KB Output is correct
26 Correct 397 ms 56880 KB Output is correct
27 Correct 15 ms 3784 KB Output is correct