oj.uz

Submission #537497

# Submission time Handle Problem Language Result Execution time Memory
537497 2022-03-15T07:26:08 Z Hydroxic_Acid Planine (COCI21_planine) C++17
20 / 110
 1031 ms 8684 KB 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define int long long

double n, h;
vector<pair<double, double> > arr;

bool comp(pair<double, double> i1, pair<double, double> i2){
	return i1.second<i2.second;
}

signed main(){
	//freopen("test.txt", "r", stdin);
	cin >> n >> h;
	if(n == 3){
		cout << 0; return 0;
	}
	double prex = 0;
	double prey = 0;
	for(int i = 0; i < n; i++){
		double x, y; cin >> x >> y;
		if(i == 0 || i == n - 1) continue;
		if(i % 2 && i != 1){
			arr[(int)arr.size() - 1].second = prex + ((h - prey) * (x - prex) / (y - prey));
		}
		else if(i%2 == 0){
			arr.push_back(make_pair(x - ((h - y) * (x - prex)/(prey - y)), 0));
			//cout << (h - y) << " " << (x - prex) << " " << prey - y << "\n" << ((h - y) * (x - prex)/(prey - y)) << "\n";
		}
		prex = x; prey = y;
	}
	sort(arr.begin(), arr.end(), comp);
	int cnt = 1;
	double eest = arr[0].second;
	//cout << arr[0].first << " " << arr[0].second << "\n";
	for(int i = 1; i < (int)arr.size(); i++){
		//cout << arr[i].first << " " << arr[i].second << "\n";
		if(arr[i].first <= eest) continue;
		eest = arr[i].second; cnt++;
	}
	cout << cnt;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 468 KB Output is correct
2 Correct 13 ms 468 KB Output is correct
3 Correct 12 ms 468 KB Output is correct
4 Correct 88 ms 1428 KB Output is correct
5 Correct 95 ms 1392 KB Output is correct
6 Correct 118 ms 1356 KB Output is correct
7 Correct 919 ms 8648 KB Output is correct
8 Correct 968 ms 8684 KB Output is correct
9 Correct 1031 ms 8544 KB Output is correct

Subtask #2
0 / 30.0

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

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 468 KB Output is correct
2 Correct 13 ms 468 KB Output is correct
3 Correct 12 ms 468 KB Output is correct
4 Correct 88 ms 1428 KB Output is correct
5 Correct 95 ms 1392 KB Output is correct
6 Correct 118 ms 1356 KB Output is correct
7 Correct 919 ms 8648 KB Output is correct
8 Correct 968 ms 8684 KB Output is correct
9 Correct 1031 ms 8544 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Incorrect 3 ms 212 KB Output isn't correct
12 Halted 0 ms 0 KB -