oj.uz

Submission #538302

# Submission time Handle Problem Language Result Execution time Memory
538302 2022-03-16T14:53:32 Z hmm789 Planine (COCI21_planine) C++14
20 / 110
 232 ms 33328 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define double long double

const double EPS = 1e-9; 

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, h, ans = 0, idx = -1;
  	double last = -1e18;
	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+EPS) {
			ans++;
			last = pos[i].first;
		}
	}
	cout << ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 4 ms 740 KB Output is correct
3 Correct 5 ms 724 KB Output is correct
4 Correct 27 ms 4308 KB Output is correct
5 Correct 23 ms 4428 KB Output is correct
6 Correct 24 ms 4556 KB Output is correct
7 Correct 194 ms 33328 KB Output is correct
8 Correct 213 ms 33324 KB Output is correct
9 Correct 232 ms 33212 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 336 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 724 KB Output is correct
2 Correct 4 ms 740 KB Output is correct
3 Correct 5 ms 724 KB Output is correct
4 Correct 27 ms 4308 KB Output is correct
5 Correct 23 ms 4428 KB Output is correct
6 Correct 24 ms 4556 KB Output is correct
7 Correct 194 ms 33328 KB Output is correct
8 Correct 213 ms 33324 KB Output is correct
9 Correct 232 ms 33212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Incorrect 1 ms 336 KB Output isn't correct
12 Halted 0 ms 0 KB -