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
|