QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#660774 | #2140. Lots of Parabolas | SorahISA# | AC ✓ | 460ms | 8088kb | C++23 | 11.8kb | 2024-10-20 13:17:21 | 2024-10-20 13:17:21 |
Judging History
answer
#ifndef SorahISA
#define SorahISA
#include SorahISA __FILE__ SorahISA
const double eps = 1e-9;
void solve() {
int N; cin >> N;
double lb = -1e18, ub = 1e18;
vector<array<double, 3>> parabola(N);
for (auto &[a, b, c] : parabola) {
cin >> a >> b >> c;
if (a > 0) chmax(lb, c - b*b/(4*a));
if (a < 0) chmin(ub, c - b*b/(4*a));
}
// debug(lb, ub);
if (lb < -9e17) { cout << "0.0 -1000000000000000000.0" << "\n"; return; }
if (ub > 9e17) { cout << "0.0 1000000000000000000.0" << "\n"; return; }
double _x, _y;
auto check = [&](double y) -> int {
double lo = -1e18, hi = 1e18;
for (auto [a, b, c] : parabola) {
double b2_4ac = b*b - 4*a*(c-y);
double x1 = (-b - sqrtl(b2_4ac)) / (2*a), x2 = (-b + sqrtl(b2_4ac)) / (2*a);
chmax(lo, min(x1, x2)), chmin(hi, max(x1, x2));
}
double x = (lo + hi) / 2.0;
int cnt = 0;
for (auto [a, b, c] : parabola) {
if (a > 0 and y - a*x*x - b*x - c >= -eps) ++cnt;
if (a < 0 and a*x*x + b*x + c - y >= -eps) ++cnt;
}
// debug(x, y, cnt);
_x = x, _y = y;
return cnt;
};
double y_lo = lb, y_hi = ub;
for (int _round = 1; _round <= 80; ++_round) {
double y0 = (y_lo + y_lo + y_hi) / 3.0;
double y1 = (y_lo + y_hi + y_hi) / 3.0;
if (check(y0) < check(y1)) y_lo = y0;
else y_hi = y1;
}
cout << fixed << setprecision(15) << _x << " ";
cout << fixed << setprecision(15) << _y << "\n";
}
int32_t main() {
fastIO();
int t = 1; // cin >> t;
for (int _ = 1; _ <= t; ++_) {
// cout << "Case #" << _ << ": ";
solve();
}
return 0;
}
#else
#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// #include <bits/extc++.h>
// #include <tr2/dynamic_bitset>
using i64 = long long;
using i128 = __int128;
#define int i64
using f80 = long double;
using f128 = __float128;
#define double f80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;
// #define X first
// #define Y second
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())
// template <size_t D, typename T> struct Vec : vector<Vec<D-1, T>> {
// static_assert(D >= 1, "Vector dimension must be greater than zero!");
// template <typename... Args> Vec(int n = 0, Args... args) : vector<Vec<D-1, T>>(n, Vec<D-1, T>(args...)) {}
// };
// template <typename T> struct Vec<1, T> : vector<T> {
// Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {}
// };
#ifdef local
#define fastIO() void()
#define debug(...) \
_color.emplace_back("\u001b[31m"), \
fprintf(stderr, "%sAt [%s], line %d: (%s) = ", _color.back().c_str(), __FUNCTION__, __LINE__, #__VA_ARGS__), \
_do(__VA_ARGS__), _color.pop_back(), \
fprintf(stderr, "%s", _color.back().c_str())
#define print(...) \
fprintf(stdout, "%s", "\u001b[36m"), \
_P(__VA_ARGS__), \
fprintf(stdout, "%s", "\u001b[0m")
deque<string> _color{"\u001b[0m"};
template <typename T> concept is_string = is_same_v<T, string&> or is_same_v<T, const string&>;
template <typename T> concept is_iterable = requires (T _t) { begin(_t); };
template <typename T> inline void _print_err(T &&_t);
template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>);
template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &);
template <size_t I, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(const tuple<U...> &_t);
template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &);
template <size_t I, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(tuple<U...> &_t);
template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu);
inline void _do() { cerr << "\n"; }
template <typename T> inline void _do(T &&_t) { _print_err(_t), cerr << "\n"; }
template <typename T, typename ...U> inline void _do(T &&_t, U &&..._u) { _print_err(_t), cerr << ", ", _do(_u...); }
#else
#define fastIO() cin.tie(0)->sync_with_stdio(0)
#define debug(...) void()
#define print(...) _P(__VA_ARGS__)
#endif
inline void _P() { cout << "\n"; }
template <typename T> inline void _P(T &&_t) { cout << _t << "\n"; }
template <typename T, typename ...U> inline void _P(T &&_t, U &&..._u) { cout << _t << " ", _P(_u...); }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int getRand(int L, int R) {
if (L > R) swap(L, R);
return (int)(rng() % ((uint64_t)R - L + 1) + L);
}
template <typename T, typename U> bool chmin(T &lhs, U rhs) { return lhs > rhs ? lhs = rhs, 1 : 0; }
template <typename T, typename U> bool chmax(T &lhs, U rhs) { return lhs < rhs ? lhs = rhs, 1 : 0; }
/// below are Fast I/O and _print_err templates ///
/*
/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///
#include <unistd.h>
const int S = 65536;
int OP = 0;
char OB[S];
inline char RC() {
static char buf[S], *p = buf, *q = buf;
return p == q and (q = (p = buf) + read(0, buf, S)) == buf ? -1 : *p++;
}
inline int RI() {
static char c;
int a;
while (((c = RC()) < '0' or c > '9') and c != '-' and c != -1);
if (c == '-') {
a = 0;
while ((c = RC()) >= '0' and c <= '9') a *= 10, a -= c ^ '0';
}
else {
a = c ^ '0';
while ((c = RC()) >= '0' and c <= '9') a *= 10, a += c ^ '0';
}
return a;
}
inline void WI(int n, char c = '\n') {
static char buf[20], p;
if (n == 0) OB[OP++] = '0';
p = 0;
if (n < 0) {
OB[OP++] = '-';
while (n) buf[p++] = '0' - (n % 10), n /= 10;
}
else {
while (n) buf[p++] = '0' + (n % 10), n /= 10;
}
for (--p; p >= 0; --p) OB[OP++] = buf[p];
OB[OP++] = c;
if (OP > S-20) write(1, OB, OP), OP = 0;
}
/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///
*/
#ifdef local
template <typename T> inline void _print_err(T &&_t) { cerr << _t; }
template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>) {
_color.emplace_back(_color.back()), ++_color.back()[3];
cerr << _color.back() << "[";
for (bool _first = true; auto &_x : _t) {
if (!_first) cerr << ", ";
_print_err(_x), _first = false;
}
cerr << "]" << (_color.pop_back(), _color.back());
}
template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu) {
_color.emplace_back(_color.back()), ++_color.back()[3];
cerr << _color.back() << "(";
_print_err(_tu.first), cerr << ", ", _print_err(_tu.second);
cerr << ")" << (_color.pop_back(), _color.back());
return os;
}
template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &) {
cerr << ")" << (_color.pop_back(), _color.back());
}
template <size_t I = 0, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(const tuple<U...> &_t) {
if (!I) {
_color.emplace_back(_color.back()), ++_color.back()[3];
cerr << _color.back();
}
cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}
template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &) {
cerr << ")" << (_color.pop_back(), _color.back());
}
template <size_t I = 0, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(tuple<U...> &_t) {
if (!I) {
_color.emplace_back(_color.back()), ++_color.back()[3];
cerr << _color.back();
}
cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}
#endif
#endif
/**
*
*
*
* iiiiii iiiiiiiiii iiiiiiiiiiiiii
* iiiiiiiiiiiii iiiiiii iiii iiiiiiiiiiiiiii ii iiii
* iiiiiiii iiiiiiiii iiii iiii iii iii iiiiiiiiii
* iiiiiii iiiiii iiii iiii ii iiiiiiiiii iiii iiii
* iiiiii iiiii iiii iiii iii iiii iiiiiiiiiiiiiiiii ii
* iiiiii iiiiiii iiiiiii iiiiiiii iii iiiiiiiiiiiiii iii iiii
* iiiiii iiiiiii iiiii ii iiii iiiiiiiiiii iiii iii iiii iiii iii
* iiiii iiiiiiii ii iiiii iiii iiiiiiiii iii iii iii iii ii iiii
* iiiiii iiiiiiii iiiii iiiii iiiiiiiiiiiiiiii iii iii ii iii iii iiii
* iiiii iiiiii iiii iiiiii iiiiiii iii iii iiii ii i ii iii iii
* iiiiii iiii iiiiiiiiiiiiiii iii iiii iiiii iii ii iii iii ii
* iiiii iiiiiiii iiiiiiiiii iiii iiiiiiiii ii iii ii
* iiiii iiiiii iiii iiiii iii ii ii i
* iiiiii iiiiiiii iiiii iiiii ii ii ii
* iiiii iiii iiii iiiiiiiiiiii ii
* iii iiii iiii iiiiiiii
* iiiii iiii
* iiii iiii
* iiii iiiii
* iii iiiii
* iii iiiii
* iii iiiiii
* iiiiiiiii
* iiiiii
*
*
*
**/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3800kb
input:
4 1 2 3 1 -3 -5 -1 3 4 -2 4 6
output:
-0.500000000416647 2.249999999333366
result:
ok Point (-0.5000000, 2.2500000)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
1 -22 -12 39
output:
0.0 -1000000000000000000.0
result:
ok Point (0.0000000, -1000000000000000000.0000000)
Test #3:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
1 26 88 45
output:
0.0 1000000000000000000.0
result:
ok Point (0.0000000, 1000000000000000000.0000000)
Test #4:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
2 4 -1 1 -4 4 3
output:
0.125000000000000 0.937500000000025
result:
ok Point (0.1250000, 0.9375000)
Test #5:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
2 -4 -3 -1 -2 0 2
output:
0.0 -1000000000000000000.0
result:
ok Point (0.0000000, -1000000000000000000.0000000)
Test #6:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
2 2 9 7 5 9 0
output:
0.0 1000000000000000000.0
result:
ok Point (0.0000000, 1000000000000000000.0000000)
Test #7:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
20 -6 -41 -65 -1 -11 -22 -8 -61 -113 7 56 109 -4 -40 -87 -9 -82 -175 8 55 87 8 67 140 -6 -43 -64 -2 -18 -28 9 76 159 2 18 41 3 34 88 -10 -86 -174 3 30 66 8 71 153 1 4 -1 -6 -48 -88 -3 -28 -52 7 51 91
output:
-4.243398113298714 0.631689056395245
result:
ok Point (-4.2433981, 0.6316891)
Test #8:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
20 11 -155 -190 -46 450 -439 33 -348 -52 -8 348 434 -9 415 244 27 -294 -73 -14 303 -332 12 -197 294 -26 405 111 -41 475 161 4 -297 123 35 -483 238 21 -271 339 -41 386 -316 20 -257 -424 1 -178 -219 -37 369 -183 12 -64 -487 -40 465 385 -21 245 20
output:
5.872180451129840 -449.029509865723143
result:
ok Point (5.8721805, -449.0295099)
Test #9:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
20 -28 662 -2672 9 -338 1137 -6 449 -1877 -5 397 -1133 -31 725 -2794 11 -338 1167 -29 727 -2831 -12 553 -1595 15 -428 1059 -2 146 -773 19 -524 2151 13 -541 2115 -3 520 -2269 5 -331 1484 20 -531 1662 2 -402 1117 -5 343 -1650 -4 216 -407 17 -440 1222 2 -235 957
output:
15.109339966206526 -1428.743212219446273
result:
ok Point (15.1093400, -1428.7432122)
Test #10:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
40 -27 127 -124 -9 8 53 11 -77 90 -12 45 -21 -25 106 -97 -8 50 -45 -19 76 -46 19 -111 126 -3 14 -2 -3 4 31 -21 116 -124 2 -36 64 9 -22 -7 21 -118 121 -35 117 -64 10 -58 50 32 -106 64 15 -45 20 3 -49 77 6 -5 -46 27 -98 78 -21 120 -124 -10 17 39 -10 33 -2 10 -61 75 -35 171 -198 -37 116 -50 -10 23 30 3...
output:
2.255135798228201 4.218358154327909
result:
ok Point (2.2551358, 4.2183582)
Test #11:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
40 -27 -87 -64 -9 -48 -43 -8 -47 -24 -34 -97 -43 -19 -42 -7 -22 -73 -47 -2 -20 23 -5 -3 42 -25 -53 6 -19 -66 -6 -37 -96 -45 -4 -18 -12 -13 -50 -9 -14 -42 -10 -27 -87 -64 -3 9 41 -12 -31 9 -19 -59 -30 -8 -32 5 -9 -52 -5 -2 -33 -44 -1 -21 4 -2 16 49 -30 -65 5 -25 -52 11 -35 -106 -65 -5 -33 -29 -27 -49...
output:
0.0 -1000000000000000000.0
result:
ok Point (0.0000000, -1000000000000000000.0000000)
Test #12:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
40 30 83 45 2 -7 -26 5 16 -27 29 98 66 27 75 22 8 14 -18 2 -14 -32 15 33 2 1 -7 -56 18 54 32 11 55 25 17 49 3 27 81 32 9 66 61 1 -33 -63 25 82 25 27 95 63 19 50 -5 18 86 60 29 116 77 25 75 20 17 56 17 33 126 80 37 141 105 35 107 56 25 81 34 23 78 24 5 -6 -34 1 -9 -54 13 55 19 12 20 -2 22 54 -5 4 -11...
output:
0.0 1000000000000000000.0
result:
ok Point (0.0000000, 1000000000000000000.0000000)
Test #13:
score: 0
Accepted
time: 3ms
memory: 3920kb
input:
1000 -6 -502 -10522 -3 -247 -5101 -9 -746 -15479 8 654 13333 1 86 1820 -6 -493 -10143 9 744 15345 2 174 3747 6 503 10502 -6 -493 -10151 -7 -582 -12113 -10 -826 -17079 6 499 10336 9 742 15263 -1 -91 -2076 -7 -581 -12070 7 580 11982 -3 -252 -5305 -3 -255 -5435 1 88 1903 -11 -897 -18302 10 826 17020 -3...
output:
-41.677124344526960 -26.697383522463069
result:
ok Point (-41.6771243, -26.6973835)
Test #14:
score: 0
Accepted
time: 3ms
memory: 3916kb
input:
1000 -166 -2543 -9416 176 2467 7478 -410 -5077 -14109 153 2052 6285 -20 -875 -3813 -131 -1726 -5046 -192 -2643 -7536 89 1375 4584 23 938 3475 160 2598 8283 -57 -915 -3052 78 1661 5492 252 3409 10190 110 2021 6478 201 2943 9107 -124 -1836 -5559 -120 -2077 -8334 -179 -2716 -9419 -142 -2315 -8410 -170 ...
output:
-8.014006773521737 17.290559292194331
result:
ok Point (-8.0140068, 17.2905593)
Test #15:
score: 0
Accepted
time: 43ms
memory: 3864kb
input:
10000 9 -798 17696 8 -699 15275 9 -784 17082 -9 797 -17624 -5 440 -9659 1 -86 1862 -3 265 -5828 -2 176 -3848 3 -265 5865 -11 964 -21105 -10 870 -18903 -1 83 -1694 -1 89 -1955 8 -702 15407 8 -698 15230 -2 173 -3717 -2 167 -3458 1 -89 1983 -11 959 -20882 11 -968 21305 -1 96 -2269 -9 801 -17797 -6 517 ...
output:
43.828835390438839 14.322270558790799
result:
ok Point (43.8288354, 14.3222706)
Test #16:
score: 0
Accepted
time: 43ms
memory: 3872kb
input:
10000 -421 14556 -124781 -124 3579 -24534 -531 18585 -161507 -616 21639 -189351 298 -10130 84921 -620 21770 -190491 -9 -399 10186 473 -16314 140202 443 -15338 132570 -828 29509 -262207 -653 23405 -208976 35 -923 4934 -366 12616 -107602 -835 29380 -257754 711 -24721 214343 152 -4787 36687 -454 16420 ...
output:
16.931818181823095 24.380165288173988
result:
ok Point (16.9318182, 24.3801653)
Test #17:
score: 0
Accepted
time: 455ms
memory: 8088kb
input:
100000 -2 63 -524 7 -230 1846 2 -76 676 -3 111 -1051 9 -309 2615 -6 193 -1572 5 -162 1266 4 -135 1100 -8 273 -2356 4 -145 1275 -1 35 -335 2 -64 471 -6 212 -1903 10 -346 2955 7 -247 2143 7 -243 2073 -2 64 -536 5 -164 1307 -4 147 -1376 2 -63 453 8 -282 2438 -8 276 -2406 8 -277 2359 -8 269 -2288 9 -311...
output:
17.058823529448072 -33.314878893287192
result:
ok Point (17.0588235, -33.3148789)
Test #18:
score: 0
Accepted
time: 460ms
memory: 7668kb
input:
100000 4 -168 -13660 -150 -11449 -217016 -41 -2841 -48412 -5 19 9797 -37 -2917 -56947 -34 -2174 -32412 4 -51 -7991 -14 -965 -16295 176 13449 254899 33 2118 31281 -25 -1424 -16827 -127 -9641 -181637 9 41 -13903 -5 83 11897 -146 -11529 -226526 150 11740 228177 -45 -3572 -70102 52 3751 66954 -24 -1172 ...
output:
-36.830596051088707 -33.549311274575531
result:
ok Point (-36.8305961, -33.5493113)
Test #19:
score: 0
Accepted
time: 1ms
memory: 3880kb
input:
100 -37 2220 -28638 -25 1500 -18582 13 -780 8158 35 -2100 26902 41 -2460 31846 33 -1980 25238 -7 420 -2958 19 -1140 13366 -47 2820 -36798 -50 3000 -39207 30 -1800 22727 -46 2760 -35991 22 -1320 15943 -2 120 1497 -43 2580 -33558 -35 2100 -26982 -31 1860 -23646 15 -900 9902 -13 780 -8238 -20 1200 -143...
output:
30.000000000000000 -3373.999999999945463
result:
ok Point (30.0000000, -3374.0000000)
Test #20:
score: 0
Accepted
time: 3ms
memory: 3900kb
input:
1000 425 -16150 -360507 367 -13946 -335509 -480 18240 390479 -101 3838 307099 32 -1216 -322779 196 -7448 -300967 -285 10830 311699 -59 2242 315541 -408 15504 352535 299 -11362 -314769 -186 7068 300809 289 -10982 -312499 -400 15200 348959 286 -10868 -311857 -69 2622 313211 44 -1672 -319359 187 -7106 ...
output:
19.000000000000000 -333307.999999994547352
result:
ok Point (19.0000000, -333308.0000000)
Test #21:
score: 0
Accepted
time: 1ms
memory: 3872kb
input:
100 -46 0 2115 20 1200 98 21 1260 957 -40 0 1599 -48 0 2303 40 2400 16898 44 2640 20162 6 360 -12138 26 1560 5222 4 240 -13918 -8 0 63 -41 0 1680 -28 0 783 -7 0 48 7 420 -11251 2 120 -15706 -50 0 2499 39 2340 16077 -45 0 2024 38 2280 15254 -11 0 120 12 720 -6846 -4 0 15 43 2580 19349 -36 0 1295 -37 ...
output:
-15.100000000099255 -8901.500000148876335
result:
ok Point (-15.1000000, -8901.5000001)
Test #22:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
200 6 300 -13785 -77 -1041 6339 -19 7 -1320 70 1708 -10263 4 200 -15015 -24 240 -22 1 50 -16875 23 1150 -3653 34 1154 -8803 9 2019 -12750 -10 100 -148 -43 430 776 -145 -683 8289 48 1298 -9257 15 1451 -9707 26 1300 -1925 8 400 -12563 31 1936 -8437 68 1315 -9083 -15 -2032 9169 -8 80 -134 -18 180 -124 ...
output:
-10.013828004505739 -8768.751567443285648
result:
ok Point (-10.0138280, -8768.7515674)
Test #23:
score: 0
Accepted
time: 3ms
memory: 3912kb
input:
1000 -97 1940 -316 27 1080 -15267 165 6600 13437 262 10480 10818 -197 3940 19084 -179 3580 14116 466 18640 -56094 279 11160 8421 142 5680 11298 -360 7200 93575 258 10320 11298 -123 2460 2804 -206 4120 21811 -99 1980 -124 448 17920 -46842 -301 6020 60476 390 15600 -21438 -386 7720 110371 -473 9460 17...
output:
-5.027614237538357 -12774.698432965007422
result:
ok Point (-5.0276142, -12774.6984330)
Test #24:
score: 0
Accepted
time: 458ms
memory: 7840kb
input:
100000 10754 172263 -698885 -8838 -170969 640201 10066 101427 -639428 411 98897 -487244 1885 20325 -164846 1470 109370 -454536 675 201125 -592526 1597 227993 -895510 3331 98310 -248590 -1083 -157235 261847 3290 196532 -837407 -6277 -98357 388691 -9485 -126213 680029 -903 -52026 80842 -1453 -64709 24...
output:
-12.000272204652049 -12676.914599332173166
result:
ok Point (-12.0002722, -12676.9145993)