# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
557505 |
2022-05-05T12:01:59 Z |
aryan12 |
Mobile (BOI12_mobile) |
C++17 |
|
1000 ms |
48132 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e6 + 5;
vector<pair<long double, long double> > coordinates(N);
int n, l;
bool Check(long double value)
{
// sqrt[(c[i].x - x) ^ 2 + (c[i].y - 0) ^ 2] = value
// (c[i].x - x) ^ 2 + c[i].y ^ 2 = value * value
// c[i].x - x = sqrt[(value * value) - c[i].y ^ 2]
// - x = sqrt[(value * value) - c[i].y ^ 2] - c[i].x
// x = c[i].x - sqrt[(value * value) - c[i].y ^ 2]
long double maxLeft = 0;
for(int i = 1; i <= n; i++)
{
long double cur_left = 0.0, cur_right = 0.0;
cur_left = coordinates[i].first - sqrt((value * value) - (coordinates[i].second * coordinates[i].second));
cur_right = coordinates[i].first + sqrt((value * value) - (coordinates[i].second * coordinates[i].second));
if(cur_left <= maxLeft)
{
maxLeft = max(maxLeft, cur_right);
}
}
return (maxLeft >= l);
}
void Solve()
{
cin >> n >> l;
for(int i = 1; i <= n; i++)
{
cin >> coordinates[i].first >> coordinates[i].second;
}
long double left = 0, right = 1e9;
long double ans = right + 1;
int cnt = 0;
while(cnt < 60)
{
// cout << "left = " << left << ", right = " << right << "\n";
cnt++;
long double mid = (left + right) / 2;
if(Check(mid))
{
right = mid;
ans = mid;
}
else
{
left = mid;
}
}
cout << fixed << setprecision(8) << ans << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
31572 KB |
Output is correct |
2 |
Correct |
26 ms |
31648 KB |
Output is correct |
3 |
Correct |
25 ms |
31564 KB |
Output is correct |
4 |
Correct |
26 ms |
31616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
31644 KB |
Output is correct |
2 |
Correct |
27 ms |
31552 KB |
Output is correct |
3 |
Correct |
26 ms |
31644 KB |
Output is correct |
4 |
Correct |
27 ms |
31548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
31564 KB |
Output is correct |
2 |
Correct |
28 ms |
31608 KB |
Output is correct |
3 |
Correct |
30 ms |
31588 KB |
Output is correct |
4 |
Correct |
27 ms |
31640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
31656 KB |
Output is correct |
2 |
Correct |
32 ms |
31648 KB |
Output is correct |
3 |
Correct |
31 ms |
31700 KB |
Output is correct |
4 |
Correct |
38 ms |
31668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
31652 KB |
Output is correct |
2 |
Correct |
30 ms |
31660 KB |
Output is correct |
3 |
Correct |
31 ms |
31572 KB |
Output is correct |
4 |
Correct |
36 ms |
31700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
31680 KB |
Output is correct |
2 |
Correct |
32 ms |
31712 KB |
Output is correct |
3 |
Correct |
31 ms |
31608 KB |
Output is correct |
4 |
Correct |
37 ms |
31700 KB |
Output is correct |
5 |
Correct |
35 ms |
31576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
172 ms |
32428 KB |
Output is correct |
2 |
Correct |
94 ms |
32648 KB |
Output is correct |
3 |
Correct |
88 ms |
32140 KB |
Output is correct |
4 |
Correct |
214 ms |
32736 KB |
Output is correct |
5 |
Correct |
125 ms |
32028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
193 ms |
32488 KB |
Output is correct |
2 |
Correct |
190 ms |
32448 KB |
Output is correct |
3 |
Correct |
212 ms |
32664 KB |
Output is correct |
4 |
Correct |
228 ms |
32860 KB |
Output is correct |
5 |
Correct |
253 ms |
33032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
91 ms |
32328 KB |
Output is correct |
2 |
Correct |
91 ms |
32716 KB |
Output is correct |
3 |
Correct |
134 ms |
32668 KB |
Output is correct |
4 |
Correct |
309 ms |
33484 KB |
Output is correct |
5 |
Correct |
215 ms |
32568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
108 ms |
33100 KB |
Output is correct |
2 |
Correct |
105 ms |
33036 KB |
Output is correct |
3 |
Correct |
141 ms |
32664 KB |
Output is correct |
4 |
Correct |
311 ms |
33672 KB |
Output is correct |
5 |
Correct |
259 ms |
32772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
109 ms |
33164 KB |
Output is correct |
2 |
Correct |
104 ms |
33052 KB |
Output is correct |
3 |
Correct |
152 ms |
32676 KB |
Output is correct |
4 |
Correct |
303 ms |
33568 KB |
Output is correct |
5 |
Correct |
257 ms |
32912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
394 ms |
35940 KB |
Output is correct |
2 |
Correct |
428 ms |
39372 KB |
Output is correct |
3 |
Correct |
438 ms |
38800 KB |
Output is correct |
4 |
Execution timed out |
1073 ms |
41232 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
435 ms |
39888 KB |
Output is correct |
2 |
Execution timed out |
1014 ms |
38292 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
492 ms |
36820 KB |
Output is correct |
2 |
Correct |
525 ms |
41036 KB |
Output is correct |
3 |
Correct |
507 ms |
40344 KB |
Output is correct |
4 |
Execution timed out |
1076 ms |
43544 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
569 ms |
41516 KB |
Output is correct |
2 |
Execution timed out |
1090 ms |
39500 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
550 ms |
37696 KB |
Output is correct |
2 |
Correct |
591 ms |
42448 KB |
Output is correct |
3 |
Correct |
596 ms |
41752 KB |
Output is correct |
4 |
Execution timed out |
1065 ms |
45080 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
602 ms |
43188 KB |
Output is correct |
2 |
Execution timed out |
1083 ms |
40872 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
625 ms |
38536 KB |
Output is correct |
2 |
Correct |
659 ms |
44032 KB |
Output is correct |
3 |
Correct |
670 ms |
43276 KB |
Output is correct |
4 |
Execution timed out |
1036 ms |
47368 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
703 ms |
44824 KB |
Output is correct |
2 |
Execution timed out |
1094 ms |
42188 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
768 ms |
40460 KB |
Output is correct |
2 |
Correct |
852 ms |
47200 KB |
Output is correct |
3 |
Correct |
818 ms |
46192 KB |
Output is correct |
4 |
Execution timed out |
1056 ms |
47520 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
837 ms |
48132 KB |
Output is correct |
2 |
Execution timed out |
1069 ms |
44860 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |