Submission #829791

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
829791	2023-08-18T15:02:54 Z	soumyojit_sen	Mobile (BOI12_mobile)	C++14	90 / 100	1000 ms	35000 KB

mobile

#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() {
	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;
	
	for(int i = 0; i < 60; i++){
		double mid = bad + (good - bad)/2;
		if(works(mid)){
			good = mid;
		} else {
			bad = mid;
		}
	}
	cout << fixed << setprecision(6) << good;
}

Subtask #1
4.0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	300 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	296 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	3 ms	340 KB	Output is correct
2	Correct	2 ms	308 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	3 ms	364 KB	Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	424 KB	Output is correct
2	Correct	5 ms	452 KB	Output is correct
3	Correct	4 ms	412 KB	Output is correct
4	Correct	6 ms	340 KB	Output is correct

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	77 ms	1960 KB	Output is correct
2	Correct	80 ms	2024 KB	Output is correct
3	Correct	50 ms	1752 KB	Output is correct
4	Correct	79 ms	2620 KB	Output is correct
5	Correct	44 ms	1364 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	1960 KB	Output is correct
2	Correct	66 ms	1880 KB	Output is correct
3	Correct	78 ms	2096 KB	Output is correct
4	Correct	82 ms	2732 KB	Output is correct
5	Correct	101 ms	3044 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	2180 KB	Output is correct
2	Correct	77 ms	2096 KB	Output is correct
3	Correct	71 ms	2504 KB	Output is correct
4	Correct	136 ms	3760 KB	Output is correct
5	Correct	112 ms	2564 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	98 ms	2360 KB	Output is correct
2	Correct	94 ms	2300 KB	Output is correct
3	Correct	89 ms	2864 KB	Output is correct
4	Correct	123 ms	3760 KB	Output is correct
5	Correct	103 ms	3096 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	105 ms	2316 KB	Output is correct
2	Correct	94 ms	2368 KB	Output is correct
3	Correct	82 ms	2892 KB	Output is correct
4	Correct	130 ms	3764 KB	Output is correct
5	Correct	95 ms	3128 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	419 ms	8636 KB	Output is correct
2	Correct	525 ms	8632 KB	Output is correct
3	Correct	495 ms	15408 KB	Output is correct
4	Correct	576 ms	17580 KB	Output is correct
5	Correct	522 ms	14892 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	522 ms	9164 KB	Output is correct
2	Correct	585 ms	14736 KB	Output is correct
3	Correct	446 ms	13872 KB	Output is correct
4	Correct	576 ms	17460 KB	Output is correct
5	Correct	501 ms	15424 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	488 ms	10144 KB	Output is correct
2	Correct	612 ms	10060 KB	Output is correct
3	Correct	563 ms	18508 KB	Output is correct
4	Correct	706 ms	21588 KB	Output is correct
5	Correct	629 ms	17676 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	602 ms	10676 KB	Output is correct
2	Correct	704 ms	17616 KB	Output is correct
3	Correct	526 ms	16528 KB	Output is correct
4	Correct	731 ms	21344 KB	Output is correct
5	Correct	622 ms	18416 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	547 ms	11700 KB	Output is correct
2	Correct	686 ms	11636 KB	Output is correct
3	Correct	688 ms	21420 KB	Output is correct
4	Correct	850 ms	24820 KB	Output is correct
5	Correct	665 ms	20292 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	710 ms	12296 KB	Output is correct
2	Correct	798 ms	20452 KB	Output is correct
3	Correct	623 ms	19556 KB	Output is correct
4	Correct	818 ms	24640 KB	Output is correct
5	Correct	700 ms	21476 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	603 ms	13324 KB	Output is correct
2	Correct	885 ms	13212 KB	Output is correct
3	Correct	752 ms	24452 KB	Output is correct
4	Correct	942 ms	28480 KB	Output is correct
5	Correct	788 ms	23940 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	822 ms	13788 KB	Output is correct
2	Correct	883 ms	23400 KB	Output is correct
3	Correct	693 ms	22288 KB	Output is correct
4	Correct	937 ms	28184 KB	Output is correct
5	Correct	809 ms	24400 KB	Output is correct

Subtask #20
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	782 ms	17052 KB	Output is correct
2	Correct	965 ms	16344 KB	Output is correct
3	Correct	934 ms	30496 KB	Output is correct
4	Execution timed out	1070 ms	35000 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #21
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1036 ms	16852 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #829791

Compilation message