Submission #684598

#	Time	Username	Problem	Language	Result	Execution time	Memory
684598		aaggupta07	Mobile (BOI12_mobile)	C++17	0 / 100	1089 ms	52924 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 double tol = 0.00000001L;

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

int n, l;
vector<pi> towers;

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;
	vector<pd> intervals(n);

	int idx = 0;
	for(int i = 0; i < n; ++i) {
		if(towers[i].s >= p || doubleEq(towers[i].s, p)) continue;
		double dist = calcDist(i, p);
		intervals[idx].f = towers[i].f - dist;
		intervals[idx].s = towers[i].f + dist;
		++idx;
	}

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

	double start = intervals[0].f, curEnd = intervals[0].s, bestEnd = intervals[0].s;
	for(auto& i: intervals) {
		bestEnd = max(bestEnd, i.s);
		if(i.f < curEnd || doubleEq(i.f, curEnd)) {
			start = min(start, i.f);
			curEnd = max(bestEnd, curEnd);
		}
	}

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

signed main() {
	cin >> n >> l;
	towers.resize(n);
	for(pi& i: towers) cin >> i.f >> 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(5);
	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