Submission #1042245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042245		sssamui	Mobile (BOI12_mobile)	C++17	0 / 100	1079 ms	31580 KiB

mobile

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <stack>
#include <iomanip>
using namespace std;
using ld = long double;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	ld L;
	cin >> n >> L;
	vector<pair<ld, ld>> xy(n);
	for (int i = 0; i < n; i++) cin >> xy[i].first >> xy[i].second;

	ld l = 0, r = 4e9;
	int it = 45;
	while (it--)
	{
		ld m = (l + r) / 2;
		stack<pair<ld, ld>> c;
		for (int i = 0; i < n; i++) if (xy[i].second <= m)
		{
			ld sq = sqrt(m * m - xy[i].second * xy[i].second);
			ld a = fmax(0, xy[i].first - sq), b = fmin(L, xy[i].first + sq);
			while (!c.empty() && ((c.top().second >= a) || (c.top().second <= -a)))
			{
				a = fmin(a, c.top().first), b = fmax(b, c.top().second);
				c.pop();
			}

			c.push({ a, b });
		}

		if ((c.size() != 1) || ((c.top().first > 0) || (c.top().second < L))) l = m;
		else r = m;
	}

	cout << fixed << setprecision(3) << l;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5