Submission #684601

#	Time	Username	Problem	Language	Result	Execution time	Memory
684601		aaggupta07	Mobile (BOI12_mobile)	C++17	0 / 100	1096 ms	20812 KiB

mobile

// Source: https://usaco.guide/general/io

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

#define int long long
#define double long double
#define f first
#define s second
#define mp make_pair

constexpr int MAX_C = 3 * 10e9;
constexpr int MAX_N = 10e6;
constexpr double tol = 0.00000001L;

using pi = pair<int, int>;
using pd = pair<double, double>;

int n, l;
pi towers[MAX_N];

bool doubleEq(double a, double b) {
	return abs(a - b) <= tol;
}

double calcDist(int i, double d) {
	return sqrt((d * d) - (towers[i].s * towers[i].s));
}

bool check(double p) {
	// cout << "Called: " << p << endl;

	double start = MAX_C, curEnd = -1 * MAX_C, bestEnd = -1 * MAX_C;
	for(int i = 0; i < n; ++i) {
		if(abs(towers[i].s) >= p || doubleEq(abs(towers[i].s), p)) continue;

		double dist = calcDist(towers[i].s, p), d1 = towers[i].f - dist, d2 = towers[i].f + dist;
		// if(p - 6.98 <= 0.1) cout << d1 << ' ' << d2 << endl;
		bestEnd = max(bestEnd, d2);

		if(d1 < curEnd || doubleEq(d1, curEnd) || i == 0) {
			start = min(start, d1);
			curEnd = max(curEnd, bestEnd);
		}
	}

	// if(p - 6.98 <= 0.1) {
	// 	cout << "------------------" << endl;
	// 	cout << start << ' ' << curEnd << '\n';
	// 	// for(int i = 0; i < n; ++i) cout << intervals[i].f << ' ' << intervals[i].s << endl;
	// 	cout << "------------------" << endl;
	// }

	if((start < 0 || doubleEq(start, 0)) && (curEnd >= l || doubleEq(curEnd, l))) return true;
	return false;
}

signed main() {
	cin >> n >> l;
	for(int i = 0; i < n; ++i) cin >> towers[i].f >> towers[i].s;
	
	double ans = MAX_C, b = MAX_C/2;
	for(int i = 0; i < 50; ++i) {
		if((ans - b) >= 0 && check(ans - b)) ans -= b;
		b /= 2;
	}
	cout.precision(4);
	cout << fixed << ans << '\n';
}

• 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