oj.uz

Submission #829891

# Submission time Handle Problem Language Result Execution time Memory
829891 2023-08-18T15:37:45 Z soumyojit_sen Mobile (BOI12_mobile) C++14
100 / 100
 558 ms 20804 KB 
#include <bits/stdc++.h>
using namespace std;
vector<pair<double, double>> pts;
int n;
double L;

bool works(double d){
	// whether a radius of d is enough to intersect all the circles
	double currDistCovered = 0.0;
	for(int i = 0; i < n; i++){
		// find the segment covered by ith circle on the highway
		// radius^2 = yi^2 + dist^2
		double dist = sqrt(d*d - pts[i].second*pts[i].second);
		double start = pts[i].first - dist;
		double end = pts[i].first + dist;

		if(start <= currDistCovered){
			currDistCovered = max(currDistCovered, end);
		}
	}
	return currDistCovered >= L;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> L;
	pts.resize(n);
	for(int i = 0; i < n; i++) cin >> pts[i].first >> pts[i].second;

	double good = 1.5e9;
	double bad = 1.0;
	
	while(good - bad > 1e-3){
		double mid = bad + (good - bad)/2;
		//cout << fixed << setprecision(6) << i << " " << mid <<"\n" ;
		if(works(mid)){
			good = mid;
		} else {
			bad = mid;
		}
	}
	cout << fixed << setprecision(12) << good;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 328 KB Output is correct
3 Correct 2 ms 328 KB Output is correct
4 Correct 2 ms 392 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 3 ms 468 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 456 KB Output is correct
3 Correct 4 ms 440 KB Output is correct
4 Correct 3 ms 464 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 340 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1492 KB Output is correct
2 Correct 37 ms 2288 KB Output is correct
3 Correct 24 ms 1620 KB Output is correct
4 Correct 51 ms 2648 KB Output is correct
5 Correct 21 ms 1488 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1492 KB Output is correct
2 Correct 34 ms 2004 KB Output is correct
3 Correct 40 ms 2608 KB Output is correct
4 Correct 44 ms 2704 KB Output is correct
5 Correct 45 ms 3076 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1620 KB Output is correct
2 Correct 38 ms 2764 KB Output is correct
3 Correct 38 ms 2508 KB Output is correct
4 Correct 56 ms 3636 KB Output is correct
5 Correct 41 ms 2516 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1876 KB Output is correct
2 Correct 48 ms 3016 KB Output is correct
3 Correct 43 ms 2900 KB Output is correct
4 Correct 55 ms 3588 KB Output is correct
5 Correct 49 ms 3020 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1876 KB Output is correct
2 Correct 46 ms 3268 KB Output is correct
3 Correct 43 ms 2896 KB Output is correct
4 Correct 55 ms 3628 KB Output is correct
5 Correct 60 ms 3028 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 8148 KB Output is correct
2 Correct 251 ms 9176 KB Output is correct
3 Correct 246 ms 9072 KB Output is correct
4 Correct 269 ms 9148 KB Output is correct
5 Correct 245 ms 9104 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 8148 KB Output is correct
2 Correct 280 ms 9164 KB Output is correct
3 Correct 212 ms 9088 KB Output is correct
4 Correct 271 ms 9116 KB Output is correct
5 Correct 258 ms 9144 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 9684 KB Output is correct
2 Correct 282 ms 10992 KB Output is correct
3 Correct 275 ms 11992 KB Output is correct
4 Correct 332 ms 11952 KB Output is correct
5 Correct 304 ms 11944 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 9684 KB Output is correct
2 Correct 335 ms 10680 KB Output is correct
3 Correct 258 ms 11964 KB Output is correct
4 Correct 324 ms 11964 KB Output is correct
5 Correct 340 ms 11980 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 11220 KB Output is correct
2 Correct 311 ms 12488 KB Output is correct
3 Correct 316 ms 13516 KB Output is correct
4 Correct 384 ms 13548 KB Output is correct
5 Correct 336 ms 13572 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 11220 KB Output is correct
2 Correct 383 ms 12236 KB Output is correct
3 Correct 305 ms 13516 KB Output is correct
4 Correct 394 ms 13460 KB Output is correct
5 Correct 348 ms 13516 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 12756 KB Output is correct
2 Correct 386 ms 14180 KB Output is correct
3 Correct 371 ms 15228 KB Output is correct
4 Correct 464 ms 15128 KB Output is correct
5 Correct 392 ms 15152 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 12756 KB Output is correct
2 Correct 458 ms 13788 KB Output is correct
3 Correct 363 ms 13948 KB Output is correct
4 Correct 465 ms 15104 KB Output is correct
5 Correct 402 ms 15108 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 15956 KB Output is correct
2 Correct 464 ms 16916 KB Output is correct
3 Correct 448 ms 17052 KB Output is correct
4 Correct 547 ms 16080 KB Output is correct
5 Correct 521 ms 20804 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 15956 KB Output is correct
2 Correct 535 ms 16444 KB Output is correct
3 Correct 481 ms 16484 KB Output is correct
4 Correct 558 ms 15956 KB Output is correct
5 Correct 554 ms 20772 KB Output is correct