Submission #730035

#	Time	Username	Problem	Language	Result	Execution time	Memory
730035		blue	Planine (COCI21_planine)	C++17	0 / 110	7 ms	604 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define sz(x) int(x.size())

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	cin >> N;

	double h;
	cin >> h;

	double x[1+N], y[1+N];
	for(int i = 1; i <= N; i++)
	{
		cin >> x[i] >> y[i];
	}


	vector<double> lo, hi;

	// cerr << "\n\n";

	for(int i = 3; i < N; i += 2)
	{
		double sl1 = (y[i-1] - y[i])/(x[i] - x[i-1]);

		lo.push_back(x[i] - (h - y[i])/sl1);


		double sl2 = (y[i+1] - y[i])/(x[i+1] - x[i]);

		hi.push_back(x[i] + (h - y[i])/sl2);

		// cerr << sl1 << ' ' << sl2 << '\n';


		// cerr << lo.back() << ' ' << hi.back() << '\n';
	}

	int res = 1;

	double clo, chi;

	clo = lo[0];
	chi = hi[0];

	for(int i = 1; i < sz(lo); i++)
	{
		clo = max(clo, lo[i]);
		chi = min(chi, hi[i]);

		// cerr << i << " : " << clo << ' ' << chi << '\n';


		if(chi - clo < -0.000000001)
		{
			res++;
			clo = lo[i];
			chi = hi[i];
		}
	}

	cout << res << '\n';
}

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