Submission #864876

#	Time	Username	Problem	Language	Result	Execution time	Memory
864876		MisterReaper	Planine (COCI21_planine)	C++17	30 / 110	2019 ms	3628 KiB

Main

//author: Ahmet Alp Orakci
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64

#define ONLINE_JUDGE
void solve() {
	int n, h;
	cin >> n >> h;

	pair <int, int> arr[n];
	for(auto &[a, b] : arr)
		cin >> a >> b;

	vector <pair <double, double>> anss;
	for(int i = 2; i < n -2; i += 2) {
		pair <double, double> ans = {-1E6, 1E6};
		for(int j = 1; j < n; j += 2) {
			if(arr[j].second >= arr[i].second) {
				if(arr[j].first <= arr[i].first) {
					double calc = arr[i].first - double(arr[i].first - arr[j].first) * double(h - arr[i].second) / double(arr[j].second - arr[i].second);
					ans.first = max(ans.first, calc);
				} else {
					double calc = arr[i].first + double(arr[j].first - arr[i].first) * double(h - arr[i].second) / double(arr[j].second - arr[i].second);
					ans.second = min(ans.second, calc);
				}
			}
		}

		anss.push_back(ans);
	}

	sort(anss.begin(), anss.end());

	int cev = 0;
	for(int i = 0; i < int(anss.size()); i++) {
		pair <double, double> nw = anss[i];
		while(i < int(anss.size())) {
			nw.first = max(nw.first, anss[i].first);
			nw.second = min(nw.second, anss[i].second);
			//cerr << anss[i].first << " " << anss[i].second << "\n";
			if(nw.first > nw.second) {
				i--;
				break;
			}

			i++;
		}

		cev++;
	}

	cout << cev << "\n";
	
	return;
}

signed main() {
	#ifndef ONLINE_JUDGE
		freopen(".in", "r", stdin);
		freopen(".out", "w", stdout);
	#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int t = 1; //cin >> t;
	for(int i = 1; i <= t; i++) {
		solve();
	}

	return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 30 / 30
• Subtask 3: 0 / 60