Submission #1294127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294127		Jawad_Akbar_JJ	Mobile (BOI12_mobile)	C++20	0 / 100	1097 ms	47624 KiB

mobile

#include <iostream>
#include <stack>
#include <cmath>

using namespace std;
#define ld double
const int N = 1<<20;
ld x[N], y[N], xx[N], yy[N];

bool poss(int n, ld L, ld mid){
	stack<pair<ld, ld>> stk;

	mid *= mid;
	for (int i=1;i<=n;i++){
		if (y[i] > mid)
			continue;
		ld b = -2 * x[i], c = xx[i] + yy[i] - mid, sq = sqrtl(b * b - 4 * c);
		ld l = (-b - sq) * 0.5;
		ld r = (-b + sq) * 0.5;
		while (stk.size() > 0 and stk.top().first > l)
			r = max(r, stk.top().second), stk.pop();
		if (stk.size() > 0 and stk.top().second >= l)
			l = stk.top().first, r = max(r, stk.top().second), stk.pop();
		
		stk.push({l, r});
	}
	while (stk.size() > 0){
		auto [a, b] = stk.top();
		stk.pop();
		if (a <= 0 and b >= L)
			return 1;
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	ld n, L;
	cin>>n>>L;

	for (int i=1;i<=n;i++){
		int X, Y;
		cin>>X>>Y;
		x[i] = X;
		y[i] = abs(Y);
		if (i > 1 and x[i-1] == x[i] and y[i] < y[i-1])
			swap(y[i], y[i-1]);
		if (i > 1 and x[i-1] == x[i] and y[i] >= y[i-1])
			i--, n--;
	}
	for (int i=1;i<=n;i++)
		xx[i] = x[i] * x[i], yy[i] = y[i] * y[i];

	ld l = 0, r = 1e10;
	while (l + 0.0001 < r){
		ld mid = (l + r) * 0.5;

		if (poss(n, L, mid))
			r = mid;
		else
			l = mid;
	}
	printf("%.5f\n", (double) r);
}

• 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