QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#59833 | #2875. Grand Center | YaoBIG | AC ✓ | 86ms | 4996kb | C++17 | 7.0kb | 2022-11-01 18:02:55 | 2022-11-01 18:02:56 |
Judging History
answer
#include "bits/stdc++.h"
#define rep(i, a, n) for (auto i = a; i <= (n); ++i)
#define revrep(i, a, n) for (auto i = n; i >= (a); --i)
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, T b) { if (b < a) { a = b; return 1; } return 0; }
using namespace std;
template<class A, class B> string to_string(const pair<A, B> &p);
string to_string(const string s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string) s); }
string to_string(char c) { return "'" + string(1, c) + "'"; }
string to_string(bool x) { return x ? "true" : "false"; }
template<class A> string to_string(const A &v) {
bool first = 1;
string res = "{";
for (const auto &x: v) {
if (!first) res += ", ";
first = 0;
res += to_string(x);
}
res += "}";
return res;
}
template<class A, class B> string to_string(const pair<A, B> &p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
void debug_out() { cerr << endl; }
template<class H, class... T> void debug_out(const H& h, const T&... t) {
cerr << " " << to_string(h);
debug_out(t...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T>
struct Point {
using P = Point;
using type = T;
static constexpr T eps = 1e-10;
static constexpr bool isInt = is_integral_v<T>;
static int sgn(T x) { return (x > eps) - (x < -eps); }
static int cmp(T x, T y) { return sgn(x - y); }
T x, y;
P operator +(P b) const { return P{x + b.x, y + b.y}; }
P operator -(P b) const { return P{x - b.x, y - b.y}; }
P operator *(T b) const { return P{x * b, y * b}; }
P operator /(T b) const { return P{x / b, y / b}; }
bool operator ==(P b) const { return cmp(x, b.x) == 0 && cmp(y, b.y) == 0; }
bool operator <(P b) const { return cmp(x, b.x) == 0 ? cmp(y, b.y) < 0: x < b.x; }
T len2() const { return x * x + y * y; }
T len() const { return sqrt(x * x + y * y); }
// dot and cross may lead to big relative error for imprecise point when the result is relatively smaller than the input magnitude.
T cross(P b) const { return x * b.y - y * b.x; }
bool is_upper() const { return y > eps || (sgn(y) == 0 && x < -eps); } /// start-hash
// return -1 if a has smaller pollar; return 1 if a has a larger pollar; return 0 o.w.
// Taking unit makes it slower but it performs as atan2.
static int argcmp(P a, P b) {
if (a.is_upper() != b.is_upper()) return cmp(a.is_upper(), b.is_upper());
return sgn(b.cross(a));
} /// end-hash
// Returns the signed distance to line $ab$. $a$ and $b$ should be distinct.
T dis_to_line(P a, P b) const { /// start-hash
assert((a - b).len2() > P::eps);
if (isInt) return (*this - a).cross(b - a);
else return (*this - a).cross(b - a) / (b - a).len();
} /// end-hash
friend string to_string(P p) { return "(" + to_string(p.x) + ", " + to_string(p.y) + ")"; }
};
/**
* Author: Yuhao Yao
* Date: 22-10-02
* Description: Compute the intersection of Half Planes, which is a Convex hull. A Half Plane is represented by the left hind side of a directed line $ab$ (i.e. counter-clockwise).
* Please make sure the intersection of Half Planes in $ls$ is bounded.
* Also make sure that there is no HalfPlane with direction $dir() = (0, 0)$.
* If the intersection is empty, then the returned vector has a size at most 2.
* Otherwise a Convex hull is returned, which has no consectuive collinear points.
* Only works for \textbf{double} and \textbf{long double}.
* \textbf{Needed function(s): argcmp, dis_to_line}.
* Status: tested on https://official.contest.yandex.com/opencupXXII/contest/38278/problems/K/, https://www.luogu.com.cn/problem/P6505, https://qoj.ac/contest/782/problem/2162.
*/
template<class P> /// start-hash
struct HalfPlane {
P a, b; // make sure a != b.
P dir() const { return b - a; }
bool include(P p) const { return p.dis_to_line(a, b) < -P::eps; }
bool operator <(const HalfPlane &rhs) const {
return P::argcmp(dir(), rhs.dir()) < 0;
}
pair<bool, P> capLL(const HalfPlane &rhs) const {
auto s0 = (a - rhs.a).cross(rhs.dir());
auto s1 = (a - b).cross(rhs.dir());
if (P::sgn(s1) == 0) return {false, P{}};
return {true, a + (b - a) * s0 / s1};
}
}; /// end-hash
template<class P, class HP = HalfPlane<P>> /// start-hash
vector<P> HPI(vector<HalfPlane<P>> hps) {
// please make sure hps is closed.
auto Samedir = [](HP &r, HP &s) { return (r < s || s < r) == 0; };
sort(all(hps), [&](HP &r, HP &s) { return Samedir(r, s) ? s.include(r.a) : r < s; });
// assuming hps is closed then the intersect function should be fine.
auto check = [](HP &w, HP &r, HP &s) {
auto [res, p] = r.capLL(s);
if (res == 0) return false; // if r and s are parallel then it implies the intersection is empty.
return w.include(p);
};
deque<HP> q;
rep(i, 0, sz(hps) - 1) {
if (i && Samedir(hps[i], hps[i - 1])) continue;
while (sz(q) > 1 && !check(hps[i], q.end()[-2], q.end()[-1])) q.pop_back();
while (sz(q) > 1 && !check(hps[i], q[0], q[1])) q.pop_front();
q.push_back(hps[i]);
}
while (sz(q) > 2 && !check(q[0], q.end()[-2], q.end()[-1])) q.pop_back();
while (sz(q) > 2 && !check(q.back(), q[0], q[1])) q.pop_front();
vector<P> res;
rep(i, 0, sz(q) - 1) res.push_back(q[i].capLL(q[(i + 1) % sz(q)]).second);
return res;
} /// end-hash
/**
* Author: Yuhao Yao
* Date: 22-08-29
* Description: Calculate the signed area of a simple Polygon $poly$. Positive area means counter-clockwise order.
* Time: O(|poly|).
* Status: tested on https://codeforces.com/gym/101673/problem/A.
*/
template<class T>
T PolyArea(const vector<Point<T>> &poly) {
if (poly.empty()) return 0;
T sum = 0;
rep(i, 0, sz(poly) - 1) sum += (poly[i] - poly[0]).cross(poly[(i + 1) % sz(poly)] - poly[0]);
return sum / 2;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
using T = double;
using P = Point<T>;
using HP = HalfPlane<P>;
int n; cin >> n;
vector<P> as(n);
for (auto &[x, y]: as) cin >> x >> y;
vi fars(n);
int ptr = 1;
rep(i, 0, n - 1) {
P a = as[i];
P b = as[(i + 1) % n];
chmax(ptr, i + 1);
while (ptr < i + n && (b - a).cross(as[(ptr + 1) % n] - as[ptr % n]) > P::eps) {
ptr++;
}
fars[i] = ptr % n;
}
auto check = [&](T ratio) {
vector<HP> hps;
rep(i, 0, n - 1) {
auto a = as[i];
auto b = as[(i + 1) % n];
auto c = as[fars[i]];
auto d = c + (a - c) * ratio / (ratio + 1);
auto e = c + (b - c) * ratio / (ratio + 1);
hps.push_back({d, e});
}
auto hull = HPI(hps);
if (sz(hull) >= 3) return 1;
else return 0;
};
T lo = 1, hi = 2;
rep(rd, 1, 35) {
T mid = (lo + hi) / 2;
if (check(mid)) hi = mid;
else lo = mid;
}
T ans = (lo + hi) / 2;
printf("%.10f\n", (double) ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3752kb
input:
4 0 0 1 0 1 1 0 1
output:
1.0000000002
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
3 0 0 1 0 0 1
output:
2.0000000000
result:
ok found '2.0000000', expected '2.0000001', error '0.0000001'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
4 0 0 2 0 4 4 0 2
output:
1.5000000001
result:
ok found '1.5000000', expected '1.5000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
8 0 0 6 11 7 13 4 14 0 15 -4 14 -7 13 -6 11
output:
1.7222222222
result:
ok found '1.7222222', expected '1.7222223', error '0.0000000'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3720kb
input:
4 4 -9 10 5 -8 -6 3 -10
output:
1.9569892473
result:
ok found '1.9569892', expected '1.9569892', error '0.0000000'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
5 -54541 -89247 -54559 -89250 -54551 -89275 -54533 -89272 -54536 -89253
output:
1.1397459165
result:
ok found '1.1397459', expected '1.1397460', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
6 63 64 -91 -3 -25 -74 27 -67 99 -38 84 54
output:
1.2917918461
result:
ok found '1.2917918', expected '1.2917919', error '0.0000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3744kb
input:
11 80149 -14019 79767 -3293 70677 620 67779 733 62316 936 60731 -2509 60190 -5365 60638 -16930 64799 -18374 71197 -18839 74837 -18754
output:
1.1457063848
result:
ok found '1.1457064', expected '1.1457064', error '0.0000000'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
12 980 -106 993 444 995 587 774 905 326 926 -788 958 -840 942 -941 430 -948 180 -950 -894 -399 -999 914 -940
output:
1.0763530029
result:
ok found '1.0763530', expected '1.0763530', error '0.0000000'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
15 -9933 -2261 -9884 -7027 -9798 -9982 7786 -9980 9194 -9550 9669 -7656 9814 -6982 9996 -5356 9962 7650 9933 9862 5788 9995 -7631 9953 -8970 9941 -9948 9520 -9984 7224
output:
1.0370249514
result:
ok found '1.0370250', expected '1.0370250', error '0.0000000'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3720kb
input:
26 -99388 98460 -99605 95356 -99812 89330 -100000 25496 -99984 -45172 -99821 -97539 -99764 -99159 -87881 -99941 -66037 -99971 31755 -99892 91560 -99416 97988 -98836 98477 -98775 99314 -96727 99752 -92437 99780 -91600 99903 -72727 99967 -18033 99972 61721 99882 98505 96588 99737 95044 99826 91003 999...
output:
1.0054905088
result:
ok found '1.0054905', expected '1.0054905', error '0.0000000'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
4 -90193 76019 41466 -97592 -18792 61801 -64035 74971
output:
1.9537091703
result:
ok found '1.9537092', expected '1.9537092', error '0.0000000'
Test #13:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
8 99217 79790 39638 88078 -39196 59201 -91442 -51225 -82115 -69068 -60816 -93795 -292 -97330 61561 -98197
output:
1.2285461774
result:
ok found '1.2285462', expected '1.2285462', error '0.0000000'
Test #14:
score: 0
Accepted
time: 2ms
memory: 3824kb
input:
15 93718 98921 -4750 99674 -91678 96071 -95667 89757 -96751 75343 -97964 45418 -97870 -15113 -96683 -84304 -64860 -97781 -59992 -97996 -20315 -99410 73859 -94388 87556 -81689 98491 -39952 98317 81106
output:
1.0625026880
result:
ok found '1.0625027', expected '1.0625027', error '0.0000000'
Test #15:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
17 -98943 93153 -99203 74457 -99786 19261 -99575 -58504 -99021 -76417 -96128 -98912 -73903 -99976 90656 -99842 98793 -95624 99268 -91899 99786 -66679 99826 36342 99723 99328 87458 99727 56646 99866 -54215 99606 -92960 99133
output:
1.0167659906
result:
ok found '1.0167660', expected '1.0167660', error '0.0000000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
22 -74104 -99983 75292 -99939 95742 -98841 99573 -89793 99668 -67759 99865 28608 99814 55714 99323 95372 99149 98220 95153 99852 54240 99978 -61655 99969 -87344 99447 -97209 98230 -99840 86621 -99966 62349 -99972 25512 -99973 -12748 -99949 -35127 -99472 -87562 -99387 -88291 -97150 -98379
output:
1.0103928769
result:
ok found '1.0103929', expected '1.0103929', error '0.0000000'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
26 -99383 98459 -99600 95355 -99807 89329 -99995 25495 -99979 -45173 -99816 -97540 -99759 -99160 -87876 -99942 -66032 -99972 31760 -99893 91565 -99417 97993 -98837 98482 -98776 99319 -96728 99757 -92438 99785 -91601 99908 -72728 99972 -18034 99977 61720 99887 98504 96593 99736 95049 99825 91008 9992...
output:
1.0054905088
result:
ok found '1.0054905', expected '1.0054905', error '0.0000000'
Test #18:
score: 0
Accepted
time: 2ms
memory: 3824kb
input:
4 8 5 0 9 0 -9 2 -9
output:
1.7941176471
result:
ok found '1.7941176', expected '1.7941177', error '0.0000000'
Test #19:
score: 0
Accepted
time: 2ms
memory: 3648kb
input:
4 91928 71582 91925 71587 91924 71559 91930 71571
output:
1.7444444445
result:
ok found '1.7444444', expected '1.7444445', error '0.0000000'
Test #20:
score: 0
Accepted
time: 2ms
memory: 3648kb
input:
10 58 80 38 92 -38 92 -73 67 -87 48 -91 41 -92 -38 -88 -47 -57 -81 47 -87
output:
1.2106130099
result:
ok found '1.2106130', expected '1.2106130', error '0.0000000'
Test #21:
score: 0
Accepted
time: 3ms
memory: 3656kb
input:
50 29321 58885 28559 58425 26500 56598 26425 56509 24132 50853 24403 47676 24455 47476 24828 46367 25280 45398 25384 45208 27104 42961 27944 42226 28139 42077 28565 41777 29632 41159 31272 40513 32028 40321 32045 40318 33583 40117 33750 40110 34771 40126 35703 40232 37442 40677 37546 40715 38316 410...
output:
1.0259999251
result:
ok found '1.0259999', expected '1.0259999', error '0.0000000'
Test #22:
score: 0
Accepted
time: 3ms
memory: 3836kb
input:
83 319 947 154 988 125 992 11 999 0 999 -173 984 -248 968 -417 908 -558 829 -680 732 -695 718 -721 692 -849 527 -856 516 -875 483 -910 413 -916 399 -936 349 -946 322 -969 243 -981 189 -993 117 -978 -208 -966 -256 -940 -339 -927 -374 -913 -406 -900 -435 -882 -470 -845 -534 -812 -583 -757 -653 -670 -7...
output:
1.0091652907
result:
ok found '1.0091653', expected '1.0091653', error '0.0000000'
Test #23:
score: 0
Accepted
time: 6ms
memory: 3836kb
input:
553 2928 9561 2853 9584 2810 9597 2682 9633 2628 9648 2505 9681 2390 9710 2335 9723 2134 9769 2075 9782 1958 9806 1705 9853 1642 9864 1618 9868 1434 9896 1361 9906 1037 9946 915 9958 764 9970 738 9972 625 9980 542 9985 413 9991 390 9992 279 9996 189 9998 61 9999 -62 9999 -181 9998 -295 9995 -404 999...
output:
1.0002375699
result:
ok found '1.0002376', expected '1.0002376', error '0.0000000'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
4 55420 68568 -90657 3904 -65122 -88325 91518 -71805
output:
1.3416424012
result:
ok found '1.3416424', expected '1.3416424', error '0.0000000'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
20 64629 78992 52700 86846 35604 94422 33359 95146 -1942 99445 -12396 98288 -12667 98243 -17690 97271 -91679 29294 -93798 21338 -96186 -240 -92881 -25886 -84662 -46994 -80210 -54610 -78926 -56550 -9435 -99507 20256 -99027 78588 -66786 97159 -36256 89935 50433
output:
1.1161795902
result:
ok found '1.1161796', expected '1.1161796', error '0.0000000'
Test #26:
score: 0
Accepted
time: 4ms
memory: 3828kb
input:
296 -30745 -95160 -24796 -96879 -24008 -97078 -23716 -97149 -21384 -97689 -19555 -98071 -17574 -98445 -14584 -98932 -14477 -98948 -12957 -99158 -11624 -99323 -11255 -99365 -10640 -99433 -9845 -99515 -990 -99995 3139 -99950 5851 -99827 6806 -99767 7252 -99735 8874 -99604 10775 -99416 12374 -99229 131...
output:
1.0016459822
result:
ok found '1.0016460', expected '1.0016460', error '0.0000000'
Test #27:
score: 0
Accepted
time: 4ms
memory: 3988kb
input:
1379 10703 -99425 10874 -99406 11541 -99331 11584 -99326 11644 -99319 11845 -99295 12487 -99217 13064 -99142 13390 -99099 13904 -99028 14381 -98960 15049 -98860 17038 -98537 17184 -98512 17298 -98492 17969 -98372 18257 -98319 18500 -98273 19164 -98146 19317 -98116 19393 -98101 19922 -97995 20286 -97...
output:
1.0000550294
result:
ok found '1.0000550', expected '1.0000550', error '0.0000000'
Test #28:
score: 0
Accepted
time: 12ms
memory: 3932kb
input:
2083 -33234 -94315 -33070 -94373 -32613 -94532 -32222 -94666 -32104 -94706 -31857 -94789 -31575 -94883 -31262 -94987 -31049 -95057 -30735 -95159 -30474 -95243 -30263 -95310 -30074 -95370 -29825 -95448 -29439 -95568 -29027 -95694 -28653 -95806 -28388 -95885 -28256 -95924 -28056 -95983 -27608 -96113 -...
output:
1.0000160514
result:
ok found '1.0000161', expected '1.0000161', error '0.0000000'
Test #29:
score: 0
Accepted
time: 25ms
memory: 4060kb
input:
2533 -98810 15387 -98849 15133 -98907 14748 -98947 14479 -99004 14085 -99034 13872 -99057 13706 -99093 13443 -99119 13251 -99131 13161 -99185 12747 -99216 12501 -99238 12326 -99251 12221 -99263 12123 -99292 11883 -99317 11675 -99335 11521 -99363 11275 -99403 10918 -99435 10622 -99452 10463 -99478 10...
output:
1.0000083638
result:
ok found '1.0000084', expected '1.0000084', error '0.0000000'
Test #30:
score: 0
Accepted
time: 50ms
memory: 4988kb
input:
10000 2725 -68897 2726 -68897 2798 -68896 2869 -68895 2939 -68894 3008 -68893 3076 -68892 3143 -68891 3209 -68890 3274 -68889 3338 -68888 3401 -68887 3463 -68886 3524 -68885 3584 -68884 3643 -68883 3701 -68882 3758 -68881 3814 -68880 3869 -68879 3923 -68878 3976 -68877 4028 -68876 4079 -68875 4129 -...
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #31:
score: 0
Accepted
time: 64ms
memory: 4868kb
input:
9999 -7403 -78743 -7328 -78742 -7255 -78741 -7183 -78740 -7112 -78739 -7042 -78738 -6973 -78737 -6905 -78736 -6838 -78735 -6772 -78734 -6707 -78733 -6643 -78732 -6580 -78731 -6518 -78730 -6457 -78729 -6397 -78728 -6338 -78727 -6280 -78726 -6223 -78725 -6167 -78724 -6112 -78723 -6058 -78722 -6005 -78...
output:
1.0000007713
result:
ok found '1.0000008', expected '1.0000008', error '0.0000000'
Test #32:
score: 0
Accepted
time: 59ms
memory: 4860kb
input:
9998 8840 -85736 8841 -85736 8916 -85735 8990 -85734 9063 -85733 9206 -85731 9276 -85730 9345 -85729 9413 -85728 9480 -85727 9546 -85726 9611 -85725 9675 -85724 9738 -85723 9800 -85722 9921 -85720 9980 -85719 10038 -85718 10151 -85716 10206 -85715 10260 -85714 10313 -85713 10365 -85712 10466 -85710 ...
output:
1.0000008548
result:
ok found '1.0000009', expected '1.0000009', error '0.0000000'
Test #33:
score: 0
Accepted
time: 53ms
memory: 4908kb
input:
9997 -1454 -90851 -1377 -90850 -1301 -90849 -1226 -90848 -1152 -90847 -1079 -90846 -1007 -90845 -936 -90844 -866 -90843 -729 -90841 -662 -90840 -531 -90838 -404 -90836 -342 -90835 -281 -90834 -221 -90833 -162 -90832 -104 -90831 -47 -90830 9 -90829 64 -90828 118 -90827 171 -90826 223 -90825 274 -9082...
output:
1.0000013115
result:
ok found '1.0000013', expected '1.0000013', error '0.0000000'
Test #34:
score: 0
Accepted
time: 51ms
memory: 4900kb
input:
9996 4600 -90225 4601 -90225 4675 -90224 4748 -90223 4820 -90222 4891 -90221 4961 -90220 5030 -90219 5098 -90218 5165 -90217 5231 -90216 5296 -90215 5360 -90214 5423 -90213 5485 -90212 5546 -90211 5665 -90209 5723 -90208 5780 -90207 5836 -90206 5945 -90204 5998 -90203 6050 -90202 6101 -90201 6151 -9...
output:
1.0000008798
result:
ok found '1.0000009', expected '1.0000009', error '0.0000000'
Test #35:
score: 0
Accepted
time: 56ms
memory: 4848kb
input:
9995 -298 -86555 -297 -86555 -222 -86554 -148 -86553 -75 -86552 -3 -86551 68 -86550 138 -86549 207 -86548 275 -86547 342 -86546 408 -86545 473 -86544 537 -86543 600 -86542 662 -86541 783 -86539 842 -86538 900 -86537 957 -86536 1068 -86534 1122 -86533 1175 -86532 1227 -86531 1278 -86530 1328 -86529 1...
output:
1.0000010963
result:
ok found '1.0000011', expected '1.0000011', error '0.0000000'
Test #36:
score: 0
Accepted
time: 59ms
memory: 4912kb
input:
9994 3455 -94088 3456 -94088 3533 -94087 3609 -94086 3684 -94085 3831 -94083 3903 -94082 3974 -94081 4044 -94080 4113 -94079 4181 -94078 4248 -94077 4314 -94076 4379 -94075 4443 -94074 4506 -94073 4568 -94072 4629 -94071 4689 -94070 4748 -94069 4806 -94068 4863 -94067 4974 -94065 5081 -94063 5133 -9...
output:
1.0000022199
result:
ok found '1.0000022', expected '1.0000022', error '0.0000000'
Test #37:
score: 0
Accepted
time: 86ms
memory: 4904kb
input:
9999 15338 -89944 15339 -89944 15413 -89943 15486 -89942 15558 -89941 15629 -89940 15699 -89939 15768 -89938 15836 -89937 15903 -89936 15969 -89935 16034 -89934 16098 -89933 16161 -89932 16223 -89931 16284 -89930 16344 -89929 16403 -89928 16461 -89927 16518 -89926 16574 -89925 16629 -89924 16683 -89...
output:
1.0056086587
result:
ok found '1.0056087', expected '1.0056087', error '0.0000000'
Test #38:
score: 0
Accepted
time: 64ms
memory: 4880kb
input:
9998 5960 -79984 5961 -79984 6036 -79983 6110 -79982 6183 -79981 6255 -79980 6326 -79979 6396 -79978 6465 -79977 6533 -79976 6600 -79975 6666 -79974 6731 -79973 6795 -79972 6858 -79971 6920 -79970 6981 -79969 7041 -79968 7100 -79967 7158 -79966 7215 -79965 7271 -79964 7326 -79963 7380 -79962 7433 -7...
output:
1.0204112569
result:
ok found '1.0204113', expected '1.0204113', error '0.0000000'
Test #39:
score: 0
Accepted
time: 63ms
memory: 4852kb
input:
9997 -83 -89362 -82 -89362 -5 -89361 71 -89360 146 -89359 220 -89358 293 -89357 365 -89356 436 -89355 506 -89354 575 -89353 643 -89352 710 -89351 776 -89350 841 -89349 905 -89348 968 -89347 1030 -89346 1091 -89345 1151 -89344 1210 -89343 1268 -89342 1325 -89341 1381 -89340 1436 -89339 1490 -89338 15...
output:
1.0416330728
result:
ok found '1.0416331', expected '1.0416331', error '0.0000000'
Test #40:
score: 0
Accepted
time: 60ms
memory: 4752kb
input:
9996 5936 -71657 5937 -71657 6011 -71656 6084 -71655 6156 -71654 6227 -71653 6297 -71652 6366 -71651 6434 -71650 6501 -71649 6567 -71648 6632 -71647 6696 -71646 6759 -71645 6821 -71644 6882 -71643 6942 -71642 7001 -71641 7059 -71640 7116 -71639 7172 -71638 7227 -71637 7281 -71636 7334 -71635 7386 -7...
output:
1.0057261516
result:
ok found '1.0057262', expected '1.0057262', error '0.0000000'
Test #41:
score: 0
Accepted
time: 55ms
memory: 4896kb
input:
9995 9675 -80779 9676 -80779 9751 -80778 9825 -80777 9898 -80776 9970 -80775 10041 -80774 10111 -80773 10180 -80772 10248 -80771 10315 -80770 10381 -80769 10446 -80768 10510 -80767 10573 -80766 10635 -80765 10696 -80764 10756 -80763 10815 -80762 10873 -80761 10930 -80760 10986 -80759 11041 -80758 11...
output:
1.0206087356
result:
ok found '1.0206087', expected '1.0206087', error '0.0000000'
Test #42:
score: 0
Accepted
time: 66ms
memory: 4996kb
input:
9994 4060 -92187 4061 -92187 4138 -92186 4214 -92185 4289 -92184 4363 -92183 4436 -92182 4508 -92181 4579 -92180 4649 -92179 4718 -92178 4786 -92177 4853 -92176 4919 -92175 4984 -92174 5048 -92173 5111 -92172 5173 -92171 5234 -92170 5294 -92169 5353 -92168 5411 -92167 5468 -92166 5524 -92165 5579 -9...
output:
1.0416277362
result:
ok found '1.0416277', expected '1.0416278', error '0.0000000'
Test #43:
score: 0
Accepted
time: 2ms
memory: 3824kb
input:
4 7 3 3 2 3 -7 5 -8
output:
1.5000000001
result:
ok found '1.5000000', expected '1.5000000', error '0.0000000'
Test #44:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
4 96779 -5192 96777 -5192 96773 -5195 96783 -5201
output:
1.8888888889
result:
ok found '1.8888889', expected '1.8888889', error '0.0000000'
Test #45:
score: 0
Accepted
time: 2ms
memory: 3648kb
input:
24 -99859 -97470 -96124 -99283 -89730 -99640 -76970 -99864 -14506 -99913 51062 -99894 84680 -99867 95930 -98282 99301 -93606 99770 -87046 99910 -54286 99908 -17214 99847 30188 99725 91356 98811 95728 98481 96525 96123 98984 88186 99806 82187 99938 -95431 99840 -97882 99783 -99439 98679 -99906 79987 ...
output:
1.0115146963
result:
ok found '1.0115147', expected '1.0115147', error '0.0000000'
Test #46:
score: 0
Accepted
time: 2ms
memory: 3720kb
input:
19 -98173 -99824 -59365 -99908 -46360 -99917 88239 -99969 99565 -99902 99591 -99032 99876 -88755 99947 -32689 99955 43797 99896 76984 99827 99526 96550 99846 -8094 99979 -94848 99877 -96975 99263 -99662 91264 -99993 44387 -99979 -97124 -99176 -99102
output:
1.0112098313
result:
ok found '1.0112098', expected '1.0112098', error '0.0000000'
Test #47:
score: 0
Accepted
time: 2ms
memory: 3720kb
input:
5 10 -7 10 7 2 12 -6 11 -9 -8
output:
1.2796803950
result:
ok found '1.2796804', expected '1.2796804', error '0.0000000'
Test #48:
score: 0
Accepted
time: 2ms
memory: 3740kb
input:
6 -52809 -67247 -52812 -67243 -52820 -67241 -52833 -67251 -52833 -67252 -52820 -67267
output:
1.4375217543
result:
ok found '1.4375218', expected '1.4375218', error '0.0000000'
Test #49:
score: 0
Accepted
time: 22ms
memory: 4120kb
input:
2559 -69326 -72067 -69024 -72356 -68851 -72521 -68768 -72600 -68463 -72887 -68290 -73049 -68093 -73233 -67782 -73521 -67551 -73733 -67339 -73927 -67168 -74082 -66947 -74282 -66897 -74327 -66779 -74433 -66671 -74530 -66309 -74852 -66084 -75051 -65945 -75173 -65589 -75484 -65417 -75633 -65199 -75821 -...
output:
1.0000083005
result:
ok found '1.0000083', expected '1.0000083', error '0.0000000'
Test #50:
score: 0
Accepted
time: 24ms
memory: 3988kb
input:
2521 -84671 -53205 -84614 -53296 -84415 -53610 -84305 -53783 -84198 -53950 -84171 -53992 -83995 -54265 -83802 -54563 -83746 -54649 -83585 -54895 -83435 -55123 -83304 -55321 -83144 -55561 -83003 -55771 -82894 -55933 -82773 -56112 -82610 -56352 -82488 -56530 -82411 -56642 -82228 -56908 -81975 -57271 -...
output:
1.0000072792
result:
ok found '1.0000073', expected '1.0000073', error '0.0000000'
Test #51:
score: 0
Accepted
time: 14ms
memory: 3964kb
input:
1609 16500 93612 16309 93487 16086 93337 15918 93223 15798 93140 15745 93103 15574 92983 15388 92850 15370 92837 15233 92738 15102 92642 15079 92625 14913 92502 14763 92389 14726 92361 14648 92301 14376 92091 14255 91996 14064 91845 13964 91765 13811 91641 13660 91518 13521 91403 13372 91279 13316 9...
output:
1.0000264254
result:
ok found '1.0000264', expected '1.0000264', error '0.0000000'
Test #52:
score: 0
Accepted
time: 18ms
memory: 4060kb
input:
1676 -75496 32111 -75414 32024 -75239 31839 -75203 31801 -74986 31572 -74630 31200 -74554 31121 -74445 31008 -74302 30860 -74207 30762 -74106 30658 -73970 30518 -73619 30160 -73378 29915 -73276 29812 -73129 29664 -72899 29433 -72712 29246 -72409 28945 -72173 28711 -72043 28583 -71985 28526 -71764 28...
output:
1.0000227940
result:
ok found '1.0000228', expected '1.0000228', error '0.0000000'
Test #53:
score: 0
Accepted
time: 19ms
memory: 4072kb
input:
1719 -2199 97275 -2246 97162 -2255 97140 -2279 97081 -2298 97034 -2340 96929 -2378 96832 -2448 96650 -2508 96489 -2549 96377 -2577 96299 -2597 96243 -2625 96164 -2664 96052 -2693 95968 -2703 95939 -2751 95797 -2774 95728 -2802 95643 -2819 95591 -2868 95440 -2936 95226 -2991 95048 -3040 94887 -3057 9...
output:
1.0000188683
result:
ok found '1.0000189', expected '1.0000189', error '0.0000000'
Test #54:
score: 0
Accepted
time: 11ms
memory: 3928kb
input:
1329 -4595 -10731 -4207 -10390 -3685 -9931 -2918 -9256 -2431 -8827 -2187 -8612 -1449 -7961 -938 -7510 -758 -7351 -37 -6714 1519 -5336 1589 -5274 1993 -4916 2488 -4477 2807 -4194 2914 -4099 3289 -3766 3432 -3639 3808 -3305 4574 -2624 4874 -2357 5375 -1911 5439 -1854 5989 -1364 6348 -1044 7632 101 819...
output:
1.0000443777
result:
ok found '1.0000444', expected '1.0000444', error '0.0000000'
Test #55:
score: 0
Accepted
time: 11ms
memory: 3904kb
input:
1821 91451 -50903 91515 -50811 91615 -50665 91701 -50537 91789 -50405 91890 -50252 92052 -50001 92165 -49820 92281 -49633 92319 -49571 92391 -49451 92480 -49302 92561 -49164 92619 -49065 92771 -48797 92789 -48765 92817 -48715 92856 -48644 92929 -48511 92948 -48476 92981 -48415 93030 -48323 93089 -48...
output:
1.0000169325
result:
ok found '1.0000169', expected '1.0000170', error '0.0000000'
Test #56:
score: 0
Accepted
time: 15ms
memory: 4076kb
input:
1824 47433 5196 48131 5343 48385 5397 48629 5449 49242 5581 49464 5629 49621 5663 49964 5738 50277 5807 50810 5925 50968 5960 51094 5988 51722 6129 52145 6225 52800 6375 52852 6387 53120 6449 53275 6485 53648 6572 54211 6704 54514 6776 55059 6906 55196 6939 55428 6995 55725 7067 55881 7105 56275 720...
output:
1.0000176997
result:
ok found '1.0000177', expected '1.0000177', error '0.0000000'
Test #57:
score: 0
Accepted
time: 20ms
memory: 3896kb
input:
1776 53357 12034 52763 11857 52367 11738 51946 11611 51658 11524 51569 11497 51349 11430 50998 11323 50638 11213 50225 11086 50011 11020 49710 10927 49472 10853 49308 10802 49141 10750 48705 10614 48275 10479 48116 10429 48027 10401 47580 10260 47457 10221 47095 10106 46828 10021 46612 9952 46318 98...
output:
1.0000236708
result:
ok found '1.0000237', expected '1.0000237', error '0.0000000'
Test #58:
score: 0
Accepted
time: 9ms
memory: 3928kb
input:
1146 -27741 46748 -27347 46061 -27192 45791 -26898 45279 -26759 45037 -26460 44517 -26372 44364 -26307 44251 -26109 43907 -25972 43669 -25877 43504 -25749 43282 -25350 42590 -24837 41701 -24522 41156 -24400 40945 -24230 40651 -24042 40326 -23646 39642 -23467 39333 -23296 39038 -23020 38562 -22846 38...
output:
1.0000512787
result:
ok found '1.0000513', expected '1.0000513', error '0.0000000'
Test #59:
score: 0
Accepted
time: 4ms
memory: 3712kb
input:
427 49606 -77019 50075 -77903 50429 -78570 50583 -78860 50942 -79536 51917 -81371 52102 -81719 52677 -82800 52735 -82909 53124 -83640 53411 -84179 54147 -85560 54596 -86402 54762 -86713 55101 -87348 55797 -88650 56055 -89132 56108 -89231 56296 -89582 56491 -89946 56847 -90610 56956 -90813 57287 -914...
output:
1.0003974639
result:
ok found '1.0003975', expected '1.0003975', error '0.0000000'
Test #60:
score: 0
Accepted
time: 11ms
memory: 3928kb
input:
1157 -28170 84522 -28192 84554 -28261 84653 -28314 84728 -28369 84805 -28393 84838 -28412 84864 -28446 84910 -28469 84941 -28514 85001 -28543 85039 -28574 85079 -28581 85088 -28620 85138 -28664 85193 -28686 85220 -28753 85301 -28764 85314 -28783 85336 -28803 85359 -28846 85408 -28888 85454 -28917 85...
output:
1.0000513776
result:
ok found '1.0000514', expected '1.0000514', error '0.0000000'
Test #61:
score: 0
Accepted
time: 20ms
memory: 4084kb
input:
1857 -38575 35403 -38455 35188 -38422 35129 -38371 35038 -38240 34805 -38165 34672 -38082 34525 -38000 34380 -37936 34267 -37835 34089 -37728 33901 -37667 33794 -37566 33617 -37362 33261 -37176 32938 -37015 32659 -36877 32421 -36759 32218 -36607 31957 -36551 31861 -36400 31603 -36342 31504 -36291 31...
output:
1.0000211811
result:
ok found '1.0000212', expected '1.0000212', error '0.0000000'
Test #62:
score: 0
Accepted
time: 8ms
memory: 3964kb
input:
2577 87591 66244 87706 66300 87875 66383 87998 66444 88123 66506 88336 66613 88618 66756 88665 66780 88706 66801 88898 66900 88927 66915 89054 66981 89178 67046 89273 67096 89343 67133 89460 67195 89732 67341 89920 67443 90093 67538 90151 67570 90279 67641 90399 67708 90525 67779 90633 67840 90698 6...
output:
1.0000085043
result:
ok found '1.0000085', expected '1.0000085', error '0.0000000'
Test #63:
score: 0
Accepted
time: 6ms
memory: 3868kb
input:
1000 16500 93612 16309 93487 16086 93337 15918 93223 15798 93140 15745 93103 15574 92983 15388 92850 15370 92837 15233 92738 15102 92642 15079 92625 14913 92502 14763 92389 14726 92361 14648 92301 14376 92091 14255 91996 14064 91845 13964 91765 13811 91641 13660 91518 13521 91403 13372 91279 13316 9...
output:
1.3044290755
result:
ok found '1.3044291', expected '1.3044291', error '0.0000000'
Test #64:
score: 0
Accepted
time: 9ms
memory: 3904kb
input:
999 -75496 32111 -75414 32024 -75239 31839 -75203 31801 -74986 31572 -74630 31200 -74554 31121 -74445 31008 -74302 30860 -74207 30762 -74106 30658 -73970 30518 -73619 30160 -73378 29915 -73276 29812 -73129 29664 -72899 29433 -72712 29246 -72409 28945 -72173 28711 -72043 28583 -71985 28526 -71764 283...
output:
1.2945362088
result:
ok found '1.2945362', expected '1.2945362', error '0.0000000'
Test #65:
score: 0
Accepted
time: 8ms
memory: 3908kb
input:
1001 -4778 87256 -4849 86858 -4880 86681 -4925 86422 -4956 86242 -5002 85973 -5030 85807 -5089 85454 -5095 85418 -5146 85108 -5198 84787 -5230 84588 -5296 84171 -5331 83948 -5368 83709 -5407 83454 -5432 83290 -5439 83244 -5488 82919 -5495 82872 -5517 82724 -5535 82602 -5573 82344 -5595 82194 -5648 8...
output:
1.3247170239
result:
ok found '1.3247170', expected '1.3247170', error '0.0000000'
Test #66:
score: 0
Accepted
time: 4ms
memory: 3864kb
input:
998 35880 25858 36164 26123 36711 26634 37076 26975 37495 27367 37839 27689 38059 27895 38459 28270 38732 28526 39055 28829 39367 29122 39450 29200 39799 29528 40286 29986 41010 30668 41607 31231 42094 31691 42421 32000 42737 32299 43072 32616 43510 33031 43799 33305 43935 33434 44527 33996 45098 34...
output:
1.1832915994
result:
ok found '1.1832916', expected '1.1832916', error '0.0000000'
Test #67:
score: 0
Accepted
time: 8ms
memory: 3892kb
input:
1002 77100 -79741 77164 -79649 77264 -79503 77350 -79375 77438 -79243 77539 -79090 77701 -78839 77814 -78658 77930 -78471 77968 -78409 78040 -78289 78129 -78140 78210 -78002 78268 -77903 78420 -77635 78438 -77603 78466 -77553 78505 -77482 78578 -77349 78597 -77314 78630 -77253 78679 -77161 78738 -77...
output:
1.3598893551
result:
ok found '1.3598894', expected '1.3598894', error '0.0000000'
Test #68:
score: 0
Accepted
time: 4ms
memory: 3952kb
input:
997 47428 33522 48126 33669 48380 33723 48624 33775 49237 33907 49459 33955 49616 33989 49959 34064 50272 34133 50805 34251 50963 34286 51089 34314 51717 34455 52140 34551 52795 34701 52847 34713 53115 34775 53270 34811 53643 34898 54206 35030 54509 35102 55054 35232 55191 35265 55423 35321 55720 35...
output:
1.3731600226
result:
ok found '1.3731600', expected '1.3731601', error '0.0000000'
Test #69:
score: 0
Accepted
time: 10ms
memory: 3832kb
input:
1003 45893 90040 45299 89863 44903 89744 44482 89617 44194 89530 44105 89503 43885 89436 43534 89329 43174 89219 42761 89092 42547 89026 42246 88933 42008 88859 41844 88808 41677 88756 41241 88620 40811 88485 40652 88435 40563 88407 40116 88266 39993 88227 39631 88112 39364 88027 39148 87958 38854 8...
output:
1.3370343176
result:
ok found '1.3370343', expected '1.3370344', error '0.0000000'
Test #70:
score: 0
Accepted
time: 8ms
memory: 3908kb
input:
996 -65163 65340 -64769 64653 -64614 64383 -64320 63871 -64181 63629 -63882 63109 -63794 62956 -63729 62843 -63531 62499 -63394 62261 -63299 62096 -63171 61874 -62772 61182 -62259 60293 -61944 59748 -61822 59537 -61652 59243 -61464 58918 -61068 58234 -60889 57925 -60718 57630 -60442 57154 -60268 568...
output:
1.0489790563
result:
ok found '1.0489791', expected '1.0489791', error '0.0000000'
Test #71:
score: 0
Accepted
time: 10ms
memory: 3840kb
input:
995 -20231 94077 -20253 94109 -20322 94208 -20375 94283 -20430 94360 -20454 94393 -20473 94419 -20507 94465 -20530 94496 -20575 94556 -20604 94594 -20635 94634 -20642 94643 -20681 94693 -20725 94748 -20747 94775 -20814 94856 -20825 94869 -20844 94891 -20864 94914 -20907 94963 -20949 95009 -20978 950...
output:
1.0750266363
result:
ok found '1.0750266', expected '1.0750267', error '0.0000000'
Test #72:
score: 0
Accepted
time: 9ms
memory: 3948kb
input:
1003 -83704 -2568 -83584 -2783 -83551 -2842 -83500 -2933 -83369 -3166 -83294 -3299 -83211 -3446 -83129 -3591 -83065 -3704 -82964 -3882 -82857 -4070 -82796 -4177 -82695 -4354 -82491 -4710 -82305 -5033 -82144 -5312 -82006 -5550 -81888 -5753 -81736 -6014 -81680 -6110 -81529 -6368 -81471 -6467 -81420 -6...
output:
1.3689996659
result:
ok found '1.3689997', expected '1.3689997', error '0.0000000'
Test #73:
score: 0
Accepted
time: 18ms
memory: 3944kb
input:
2000 87566 13673 87681 13729 87850 13812 87973 13873 88098 13935 88311 14042 88593 14185 88640 14209 88681 14230 88873 14329 88902 14344 89029 14410 89153 14475 89248 14525 89318 14562 89435 14624 89707 14770 89895 14872 90068 14967 90126 14999 90254 15070 90374 15137 90500 15208 90608 15269 90673 1...
output:
1.1205590514
result:
ok found '1.1205591', expected '1.1205591', error '0.0000000'
Test #74:
score: 0
Accepted
time: 2ms
memory: 3740kb
input:
4 80533 -100000 80534 -100000 80534 100000 80533 100000
output:
1.0000000002
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #75:
score: 0
Accepted
time: 2ms
memory: 3740kb
input:
4 -100000 -9812 100000 -9812 100000 -9811 -100000 -9811
output:
1.0000000002
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #76:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
4 0 0 100000 0 100000 100000 0 100000
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #77:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
4 -93872 -11568 6128 -11568 6128 88432 -93872 88432
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #78:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
4 -92431 -54274 57569 -54274 57569 95726 -92431 95726
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #79:
score: 0
Accepted
time: 2ms
memory: 3828kb
input:
4 -99999 -100000 100000 -100000 100000 99999 -99999 99999
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'