Submission #00193


ソースコード

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (i64 i = 0, i##_limit = (n); i < i##_limit; ++i)
#define reps(i, s, t) for (i64 i = (s), i##_limit = (t); i <= i##_limit; ++i)
#define repr(i, s, t) for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__)
#ifndef DBG
#define trace(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U> inline bool chmax(T &a, const U &b) { return b > a && (a = b, true); }
template <class T, class U> inline bool chmin(T &a, const U &b) { return b < a && (a = b, true); }
inline i64 sigma(i64 n) { return (n * (n + 1) >> 1); }
inline i64 updiv(i64 a, i64 b) { return (a + b - 1) / b; }
inline i64 sqr(i64 n) { return n * n; }
inline string to_string(char c) { return string(1, c); }
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
template <class T>
inline vector<T> make_v(const T &initValue, size_t sz) {
return vector<T>(sz, initValue);
}
template <class T, class... Args>
inline auto make_v(const T &initValue, size_t sz, Args... args) {
return vector<decltype(make_v<T>(initValue, args...))>(sz, make_v<T>(initValue, args...));
}
inline void input() {}
template <class Head, class... Tail>
inline void input(Head &head, Tail&... tail) { cin >> head; input(tail...); }
inline void print() { cout << "\n"; }
template <class Head, class... Tail>
inline void print(Head &&head, Tail&&... tail) {
cout << head;
if (sizeof...(tail)) cout << ' ';
print(forward<Tail>(tail)...);
}
template <class T>
inline ostream& operator<< (ostream &out, const vector<T> &vec) {
static constexpr const char *delim[] = { " ", "" };
for (const auto &e : vec) out << e << delim[&e == &vec.back()];
return out;
}
// }}} End Header
struct Circle {
i64 x, r;
int leftPos() const {
return x - r;
}
int rightPos() const {
return x + r;
}
double leftPos(double h) const {
return x - sqrt(r*r - h*h);
}
double rightPos(double h) const {
return x + sqrt(r*r - h*h);
}
bool operator==(const Circle &c) const {
return x == c.x && r == c.r;
}
};
constexpr double EPS = 1e-9;
signed main()
{
ios::sync_with_stdio(false); cin.tie(nullptr);
var(int, N);
vector<Circle> C(N);
rep(i, N) {
var(int, x, r);
C[i] = {x, r};
}
Circle leftC = C[0]; // rightPos() min
Circle rightC = C[0]; // leftPos() max
for (const Circle c : C) {
if (c.rightPos() < leftC.rightPos()) {
leftC = c;
} else if (c.rightPos() == leftC.rightPos() && c.r < leftC.r) {
leftC = c;
}
if (c.leftPos() > rightC.leftPos()) {
rightC = c;
} else if (c.leftPos() == rightC.leftPos() && c.r < rightC.r) {
rightC = c;
}
}
double low = 0.0;
double high = min(leftC.r, rightC.r);
double ans = 1e6;
trace(leftC.x, leftC.r);
trace(rightC.x, rightC.r);
if (leftC == rightC) {
print(leftC.r);
return 0;
}
if (leftC.rightPos() == rightC.leftPos()) {
print(0);
return 0;
}
while(true) {
const double mid = (low + high) / 2;
if (fabs(mid - ans) < 1e-8) break;
ans = mid;
const double a = leftC.rightPos(mid);
const double b = rightC.leftPos(mid);
const bool tooHigh = (a + EPS < b);
if (tooHigh) {
high = mid;
} else {
low = mid;
}
}
cout << fixed << setprecision(7) << ans << endl;
return 0;
}

ステータス

項目 データ
問題 0009 - ヒバラ海に沈む遺跡
ユーザー名 poyo
投稿日時 2019-09-10 18:38:43
言語 C++14
状態 Wrong Answer
得点 0
ソースコード長 3902 Byte
最大実行時間 36 ms
最大メモリ使用量 2356 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
00-sample1.in AC 18 ms 476 KB
1
00-sample2.in AC 24 ms 560 KB
1
00-sample3.in AC 21 ms 516 KB
1
01_shift1.in AC 30 ms 2132 KB
1
01_shift10.in AC 31 ms 2048 KB
1
01_small_00.in AC 19 ms 436 KB
1
01_small_01.in WA 21 ms 520 KB
1
02_single1.in AC 20 ms 480 KB
1
02_single2.in AC 23 ms 432 KB
1
02_single3.in AC 16 ms 516 KB
1
10_common1.in AC 29 ms 2196 KB
1
10_common2.in AC 28 ms 2252 KB
1
20_small_area1.in AC 35 ms 2304 KB
1
20_small_area2.in AC 35 ms 2356 KB
1
30_nest_center.in AC 32 ms 2284 KB
1
30_nest_left.in AC 34 ms 2204 KB
1
30_nest_right.in AC 36 ms 2132 KB
1
100_rand_00.in AC 27 ms 476 KB
1
100_rand_01.in AC 19 ms 560 KB
1
100_rand_02.in AC 21 ms 516 KB
1
100_rand_03.in AC 28 ms 476 KB
1
100_rand_04.in AC 17 ms 564 KB
1
100_rand_05.in AC 23 ms 648 KB
1
100_rand_06.in WA 22 ms 604 KB
1
100_rand_07.in AC 19 ms 556 KB
1
100_rand_08.in AC 21 ms 640 KB
1
100_rand_09.in WA 17 ms 592 KB
1
100_rand_10.in AC 21 ms 544 KB
1
101_largerand_00.in WA 21 ms 624 KB
1
101_largerand_01.in WA 16 ms 564 KB
1
101_largerand_02.in WA 28 ms 616 KB
1
101_largerand_03.in WA 19 ms 648 KB
1
101_largerand_04.in WA 18 ms 660 KB
1