Submission #1166001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166001		aadisaini2012	Mobile (BOI12_mobile)	C++20	100 / 100	265 ms	16092 KiB

mobile

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

// Store positions of mobile towers
pair<long long, long long> towers[1000000];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int numTowers, roadLength;
	cin >> numTowers >> roadLength;
	
	// Read tower positions (x, y)
	for (int i = 0; i < numTowers; i++) {
		cin >> towers[i].first >> towers[i].second;
	}

	// Binary search for minimum radius needed
	double left = 1, right = 1.5e9;
	while (right - left > 1e-3) {  // Precision threshold
		double radius = (left + right) / 2;
		double coverage = 0;  // Current coverage along the road
		
		for (int i = 0; i < numTowers; i++) {
			// Calculate horizontal coverage range using Pythagorean theorem
			double horizontalRange = sqrt(radius * radius - towers[i].second * towers[i].second);
			double startPoint = towers[i].first - horizontalRange;
			double endPoint = towers[i].first + horizontalRange;
			
			// If this tower overlaps with current coverage, extend the coverage
			if (startPoint <= coverage) {
				coverage = max(coverage, endPoint);
			}
		}

		// Check if we covered the entire road
		if (coverage >= roadLength) {
			right = radius;  // Try smaller radius
		} else {
			left = radius;   // Need larger radius
		}
	}

	cout << fixed << setprecision(4) << left;
	return 0;
}

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