Submission #1093840

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1093840	2024-09-27T16:03:09 Z	damamila	Mobile (BOI12_mobile)	C++17	0 / 100	337 ms	21484 KB

mobile

#include <bits/stdc++.h>

using namespace std;

//~ #define int long long

int n;
double l;
vector<pair<int, int>> points;

pair<double, double> circle_intersection(int i, double r) {
	auto [x, y] = points[i];
	if (y > r) return {-1, -1}; //too far away
	double r2 = r*r;
	double y2 = y*y;
	double tmp = sqrt(r2-y2);
	double x1 = x-tmp;
	double x2 = x+tmp;
	return {x1, x2};
}

void solve() {
	double ub = 1.5e9, lb = 1;
	double m;
	while (lb+0.001 < ub) {
		m = (lb+ub)/2;
		double reach = 0;
		bool ja = 1;
		for (int i = 0; i < n; i++) {
			auto [x1, x2] = circle_intersection(i, m);
			if (reach < x1) ja = 0;
			reach = max(reach, x2);
		}
		if (reach < l) ja = 0;
		if (ja) ub = m;
		else lb = m;
	}
	cout << lb << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);  
	cin >> n >> l;
	cout << fixed << setprecision(4);
	points = vector<pair<int, int>> (n);
	for (int i = 0; i < n; i++) {
		cin >> points[i].first >> points[i].second;
		//~ points[i].second = abs(points[i].second);
	}
	//~ sort(points.begin(), points.end());
	solve();
}

Subtask #1
0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	456 KB	Output is correct
3	Incorrect	348 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #2
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Incorrect	1 ms	348 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #3
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	348 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	464 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	536 KB	Output is correct
2	Correct	2 ms	348 KB	Output is correct
3	Incorrect	2 ms	468 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	344 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	26 ms	1628 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	26 ms	1580 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	1780 KB	Output is correct
2	Incorrect	25 ms	2252 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #10
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	26 ms	2652 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #11
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	2644 KB	Output is correct
2	Incorrect	37 ms	2492 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #12
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	130 ms	7872 KB	Output is correct
2	Correct	135 ms	10428 KB	Output is correct
3	Correct	135 ms	10040 KB	Output is correct
4	Incorrect	337 ms	11856 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #13
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	128 ms	10956 KB	Output is correct
2	Incorrect	179 ms	9556 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #14
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	129 ms	9084 KB	Output is correct
2	Incorrect	150 ms	12428 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #15
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	159 ms	12792 KB	Output is correct
2	Incorrect	218 ms	11344 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #16
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	144 ms	10832 KB	Output is correct
2	Incorrect	171 ms	14324 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #17
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	174 ms	15040 KB	Output is correct
2	Incorrect	245 ms	13136 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #18
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	173 ms	12116 KB	Output is correct
2	Incorrect	203 ms	16516 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #19
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	192 ms	16976 KB	Output is correct
2	Incorrect	273 ms	15184 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #20
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	210 ms	15148 KB	Output is correct
2	Incorrect	245 ms	20560 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #21
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	272 ms	21484 KB	Output is correct
2	Incorrect	320 ms	20260 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Submission #1093840

Compilation message