# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
91779 |
2018-12-30T02:41:03 Z |
updown1 |
Mobile (BOI12_mobile) |
C++17 |
|
1000 ms |
63668 KB |
/*
binary search on the answer
to test a value x, for all the circles come up with ranges of the line that is covered if the circle has a radius x
find the minimum value x s.t. the whole line is covered
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, N)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
#define int ll
#define double long double
const int MAXN=1000000, INF=1000000000000000000;
///500,000,000
int N, L;
pair<double, double> pts[MAXN], rng[MAXN];
bool full(double rr) {
/// make the ranges
ffi {
int x = pts[i].a, y = pts[i].b;
if (y*y > rr*rr) {rng[i] = mp(0, 0); continue;}
double l = x - sqrt(rr*rr-y*y); double r = x + sqrt(rr*rr-y*y);
l = max(l, (double) 0); l = min(l, (double)L);
r = max(r, (double) 0); r = min(r, (double)L);
rng[i] = mp(l, r);
}
//exit(0);
sort(rng, rng+N);
//w<< rr<<e; ffi w<< rng[i].a s rng[i].b<<e;
/// see if the whole range is covered
double far = 0;
ffi {
if (rng[i].a > far) return false;
far = max(far, rng[i].b);
}
return far >=L;
}
main() {
//ifstream cin("test.in");
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> L;
double a = 2236067978, b = 2236067978;
ffi {
cin >> pts[i].a >> pts[i].b;
double x = pts[i].a, y = pts[i].b;
double use1 = sqrt(x*x+y*y);
double use2 = sqrt((x-L)*(x-L)+y*y);
b = min(b, max(use1, use2));
a = min(a, min(use1, use2));
}
while (b-a > .001) {
double mid = (a+b)/2;
if (full(mid)) b = mid;
else a = mid;
}
w<< fixed << setprecision(4) <<a<<e;
}
Compilation message
mobile.cpp:50:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
504 KB |
Output is correct |
2 |
Correct |
6 ms |
520 KB |
Output is correct |
3 |
Correct |
5 ms |
504 KB |
Output is correct |
4 |
Correct |
9 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
632 KB |
Output is correct |
2 |
Correct |
14 ms |
632 KB |
Output is correct |
3 |
Correct |
17 ms |
632 KB |
Output is correct |
4 |
Correct |
18 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
732 KB |
Output is correct |
2 |
Correct |
15 ms |
696 KB |
Output is correct |
3 |
Correct |
14 ms |
632 KB |
Output is correct |
4 |
Correct |
18 ms |
752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
764 KB |
Output is correct |
2 |
Correct |
14 ms |
632 KB |
Output is correct |
3 |
Correct |
16 ms |
632 KB |
Output is correct |
4 |
Correct |
20 ms |
760 KB |
Output is correct |
5 |
Correct |
12 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
308 ms |
5324 KB |
Output is correct |
2 |
Correct |
328 ms |
5468 KB |
Output is correct |
3 |
Correct |
228 ms |
4032 KB |
Output is correct |
4 |
Correct |
333 ms |
5392 KB |
Output is correct |
5 |
Correct |
125 ms |
3832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
250 ms |
5520 KB |
Output is correct |
2 |
Correct |
262 ms |
5072 KB |
Output is correct |
3 |
Correct |
327 ms |
5756 KB |
Output is correct |
4 |
Correct |
364 ms |
5624 KB |
Output is correct |
5 |
Correct |
427 ms |
6056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
279 ms |
6116 KB |
Output is correct |
2 |
Correct |
360 ms |
5732 KB |
Output is correct |
3 |
Correct |
415 ms |
5976 KB |
Output is correct |
4 |
Correct |
551 ms |
6896 KB |
Output is correct |
5 |
Correct |
306 ms |
6320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
420 ms |
6872 KB |
Output is correct |
2 |
Correct |
474 ms |
6876 KB |
Output is correct |
3 |
Correct |
452 ms |
6876 KB |
Output is correct |
4 |
Correct |
551 ms |
6904 KB |
Output is correct |
5 |
Correct |
397 ms |
6936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
453 ms |
6868 KB |
Output is correct |
2 |
Correct |
481 ms |
7032 KB |
Output is correct |
3 |
Correct |
469 ms |
6932 KB |
Output is correct |
4 |
Correct |
546 ms |
6928 KB |
Output is correct |
5 |
Correct |
400 ms |
6904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1053 ms |
31956 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1057 ms |
31968 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1066 ms |
38228 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1082 ms |
38236 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1061 ms |
44556 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1062 ms |
44484 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1076 ms |
50808 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1066 ms |
50756 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1083 ms |
63668 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1071 ms |
63584 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |