Submission #537547

#TimeUsernameProblemLanguageResultExecution timeMemory
537547hmm789Planine (COCI21_planine)C++14
0 / 110
2 ms596 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define double long double

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, h, ans = 0, last = -1e18, idx = -1;
	cin >> n >> h;
	int x[n], y[n];
	pair<double, double> pos[n/2-1];
	double m, c;
	for(int i = 0; i < n; i++) cin >> x[i] >> y[i];
	for(int i = 1; i < n; i += 2) {
		if(i != 1) {
			m = (y[i]-y[i-1])*1.0/(x[i]-x[i-1]);
			c = y[i] - m*x[i];
			pos[idx].first = (h-c)/m;
		}
		idx++;
		if(i != n-2) {
			m = (y[i]-y[i+1])*1.0/(x[i]-x[i+1]);
			c = y[i] - m*x[i];
			pos[idx].second = (h-c)/m;
		}
	}
	sort(pos, pos+n/2-1);
	for(int i = 0; i < n/2-1; i++) {
		if(pos[i].second > last) {
			ans++;
			last = pos[i].first;
		}
	}
	cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...