oj.uz

Submission #537558

# Submission time Handle Problem Language Result Execution time Memory
537558 2022-03-15T08:29:11 Z hmm789 Planine (COCI21_planine) C++14
0 / 110
 4 ms 596 KB 
#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+1e-10)) {
			ans++;
			last = (int)(pos[i].first+1e-11);
		}
	}
	cout << ans;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Incorrect 3 ms 596 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Incorrect 3 ms 596 KB Output isn't correct
4 Halted 0 ms 0 KB -