Submission #00151

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cfloat>
#include <cmath>
#include <cstring>
#include <functional>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
template<class T, class Compare = greater<T> >
using MaxHeap = priority_queue<T, vector<T>, Compare>;
template<class T, class Compare = less<T> >
using MinHeap = priority_queue<T, vector<T>, Compare>;
using llong = long long;
llong n;
llong x[100005];
llong r[100005];
pair<double, double> getCrossPoints(double base, double r, double y) {
double x = sqrt((r * r) - (y * y));
// r**2 == x**2 + y**2
return make_pair(-x + base, x + base);
}
bool f(const double y) {
bool f = true;
double lx, rx;
lx = -1e15;
rx = 1e15;
for (llong i = 0; i < n; i++) {
if (r[i] < y) f = false;
pair<double, double>p = getCrossPoints(x[i], r[i], y);
lx = max(p.first, lx);
rx = min(p.second, rx);
}
return (lx <= rx) && f;
}
int main() {
cin >> n;
for (llong i = 0; i < n; i++) {
cin >> x[i];
cin >> r[i];
}
// binary search
double valid = 0;
double invalid = 1e6 + 1;
double mid;
for (int k = 0; k < 308; k++) {
mid = (valid + invalid) / 2.0;
if (f(mid)) valid = mid;
else invalid = mid;
}
printf("%.*lf\n", DBL_DIG, valid);
return 0;
}

ステータス

項目 データ
問題 0009 - ヒバラ海に沈む遺跡
ユーザー名 ARUMAKAN
投稿日時 2019-09-10 17:30:56
言語 C++14
状態 Accepted
得点 15
ソースコード長 1554 Byte
最大実行時間 223 ms
最大メモリ使用量 2276 KB

セット

セット 得点 Cases
1 ALL 15 / 15 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
00-sample1.in AC 23 ms 604 KB
1
00-sample2.in AC 27 ms 696 KB
1
00-sample3.in AC 27 ms 536 KB
1
01_shift1.in AC 213 ms 2040 KB
1
01_shift10.in AC 223 ms 2108 KB
1
01_small_00.in AC 21 ms 524 KB
1
01_small_01.in AC 20 ms 492 KB
1
02_single1.in AC 24 ms 584 KB
1
02_single2.in AC 25 ms 416 KB
1
02_single3.in AC 20 ms 380 KB
1
10_common1.in AC 220 ms 2084 KB
1
10_common2.in AC 220 ms 2156 KB
1
20_small_area1.in AC 223 ms 2100 KB
1
20_small_area2.in AC 215 ms 2044 KB
1
30_nest_center.in AC 219 ms 2248 KB
1
30_nest_left.in AC 212 ms 2204 KB
1
30_nest_right.in AC 218 ms 2276 KB
1
100_rand_00.in AC 22 ms 596 KB
1
100_rand_01.in AC 17 ms 432 KB
1
100_rand_02.in AC 29 ms 524 KB
1
100_rand_03.in AC 22 ms 488 KB
1
100_rand_04.in AC 25 ms 452 KB
1
100_rand_05.in AC 30 ms 544 KB
1
100_rand_06.in AC 24 ms 508 KB
1
100_rand_07.in AC 23 ms 472 KB
1
100_rand_08.in AC 24 ms 564 KB
1
100_rand_09.in AC 18 ms 528 KB
1
100_rand_10.in AC 20 ms 620 KB
1
101_largerand_00.in AC 24 ms 588 KB
1
101_largerand_01.in AC 27 ms 528 KB
1
101_largerand_02.in AC 27 ms 588 KB
1
101_largerand_03.in AC 34 ms 636 KB
1
101_largerand_04.in AC 34 ms 664 KB
1