QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#61103 | #4226. Cookie Cutter | YaoBIG | AC ✓ | 2271ms | 3920kb | C++17 | 4.5kb | 2022-11-09 22:10:14 | 2022-11-09 22:10:15 |
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...);
}
#ifndef ONLINE_JUDGE
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) if(0) puts("No effect.")
#endif
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-9;
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}; }
T len2() { return x * x + y * y; }
T len() { return sqrt(x * x + y * y); }
T cross(P b) const { return x * b.y - y * b.x; }
int is_upper() const { return y > eps || (sgn(y) == 0 && x < -eps); }
static int argcmp(P a, P b) {
if (a.is_upper() != b.is_upper()) return a.is_upper() - b.is_upper();
return sgn(b.cross(a));
}
T dis_to_line(P a, P b) const {
assert((a - b).len2() > P::eps);
if (isInt) return (*this - a).cross(b - a);
else return (*this - a).cross(b - a) / (b - a).len();
}
friend string to_string(P a) { return to_string(make_pair(a.x, a.y)); }
};
template<class P>
vector<P> cutPoly(const vector<P> &poly, P a, P b) {
vector<P> res;
rep(i, 0, sz(poly) - 1) {
P p = poly[i];
P q = poly[(i + 1) % sz(poly)];
int sgn1 = P::sgn(p.dis_to_line(a, b));
int sgn2 = P::sgn(q.dis_to_line(a, b));
if (sgn1 <= 0) res.push_back(p);
if (sgn1 * sgn2 == -1) {
auto s0 = (p - a).cross(b - a);
auto s1 = (p - q).cross(b - a);
res.push_back(p + (q - p) * s0 / s1);
}
}
return res;
}
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>;
T W; int n; cin >> W >> n;
const vector<P> bs{{0, 0}, {W, 0}, {W, W}, {0, W}};
vector<P> as(n);
for (auto &[x, y]: as) cin >> x >> y;
T ans = 0;
rep(i, 0, n - 1) {
P o = as[i];
vector<P> vec;
rep(j, 0, n - 1) if (j != i) vec.push_back(as[j]);
sort(all(vec), [&](P a, P b) { return P::argcmp(a - o, b - o) < 0; });
auto SameDir = [&](P a, P b) { return P::argcmp(a - o, b - o) == 0; };
int ptr = 0, tot = sz(vec);
rep(i, 0, tot - 1) {
if (i && SameDir(vec[i], vec[i - 1])) continue;
while (ptr < i + tot && vec[ptr % tot].dis_to_line(o, vec[i]) <= P::eps) ptr++;
int c = ptr - i + 1;
auto po = cutPoly(bs, o, vec[i]);
T s = PolyArea(po);
chmax(ans, T(c) / n - s / W / W);
}
}
auto solve = [&]() {
for (auto p: as) {
auto [x, y] = p;
if (x <= W / 2 && y <= W / 2) {
P q{0, y * 2};
vector<P> vec;
int c = 0;
for (auto a: as) if (a.dis_to_line(p, q) <= P::eps) c++;
auto po = cutPoly(bs, p, q);
T s = PolyArea(po);
chmax(ans, T(c) / n - s / W / W);
}
}
};
rep(rd, 1, 4) {
solve();
for (auto &p: as) {
auto [x, y] = p;
p = P{W - y, x};
}
}
printf("%.10f\n", ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 3756kb
input:
5 8 1 1 1 2 1 3 2 1 3 1 3 4 4 1 4 2
output:
0.3750000000
result:
ok found '0.3750000', expected '0.3750000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1817ms
memory: 3704kb
input:
10000 2916 93 93 93 278 93 463 93 649 93 834 93 1019 93 1204 93 1389 93 1574 93 1760 93 1945 93 2130 93 2315 93 2500 93 2685 93 2871 93 3056 93 3241 93 3426 93 3611 93 3796 93 3982 93 4167 93 4352 93 4537 93 4722 93 4907 93 5093 93 5278 93 5463 93 5648 93 5833 93 6018 93 6204 93 6389 93 6574 93 6759...
output:
0.0093444444
result:
ok found '0.0093444', expected '0.0093444', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1808ms
memory: 3808kb
input:
10000 2916 1000 1000 1000 1151 1000 1302 1000 1453 1000 1604 1000 1755 1000 1906 1000 2057 1000 2208 1000 2358 1000 2509 1000 2660 1000 2811 1000 2962 1000 3113 1000 3264 1000 3415 1000 3566 1000 3717 1000 3868 1000 4019 1000 4170 1000 4321 1000 4472 1000 4623 1000 4774 1000 4925 1000 5075 1000 5226...
output:
0.1000000000
result:
ok found '0.1000000', expected '0.1000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 1800ms
memory: 3912kb
input:
10000 2916 50 50 50 237 50 424 50 610 50 797 50 984 50 1171 50 1358 50 1544 50 1731 50 1918 50 2105 50 2292 50 2478 50 2665 50 2852 50 3039 50 3225 50 3412 50 3599 50 3786 50 3973 50 4159 50 4346 50 4533 50 4720 50 4907 50 5093 50 5280 50 5467 50 5654 50 5841 50 6027 50 6214 50 6401 50 6588 50 6775 ...
output:
0.0135185185
result:
ok found '0.0135185', expected '0.0135185', error '0.0000000'
Test #5:
score: 0
Accepted
time: 365ms
memory: 3856kb
input:
3000 2999 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52...
output:
0.5000000000
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 2227ms
memory: 3812kb
input:
10000 3000 2291 3747 7077 9024 8698 5564 5000 4856 7265 103 6672 3043 1458 8108 17 7872 7084 6565 3127 304 6905 9627 5572 6607 1922 489 2273 7798 2548 7044 3082 4225 4242 2287 6284 2489 4802 3096 6902 8724 49 5126 5275 1878 2269 3237 9323 8048 1174 5680 5992 6262 609 433 6690 2531 9430 5618 5410 210...
output:
0.0301991336
result:
ok found '0.0301991', expected '0.0301991', error '0.0000000'
Test #7:
score: 0
Accepted
time: 2250ms
memory: 3704kb
input:
10000 3000 156 1582 2398 3319 7701 5829 4040 1938 7464 4347 111 9210 6412 541 4390 4151 2359 7197 2606 1160 594 722 1473 5727 3781 5857 3468 5814 3980 6917 1106 1389 6968 9552 9538 7438 1704 9872 9004 2595 7285 1722 3217 5133 7389 4704 7724 5553 7584 4281 4362 4220 4361 5456 7241 9044 9942 5132 9582...
output:
0.0275047475
result:
ok found '0.0275047', expected '0.0275047', error '0.0000000'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
5 2 2 3 1 4
output:
0.6800000000
result:
ok found '0.6800000', expected '0.6800000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 1788ms
memory: 3756kb
input:
10000 3000 9999 5000 9998 5010 9998 5020 9998 5031 9998 5041 9998 5052 9998 5062 9998 5073 9998 5083 9998 5094 9997 5104 9997 5115 9997 5125 9997 5136 9996 5146 9996 5157 9996 5167 9995 5177 9995 5188 9995 5198 9994 5209 9994 5219 9993 5230 9993 5240 9992 5251 9992 5261 9991 5272 9991 5282 9990 5292...
output:
0.1298015800
result:
ok found '0.1298016', expected '0.1298016', error '0.0000000'
Test #10:
score: 0
Accepted
time: 38ms
memory: 3636kb
input:
1000 999 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 ...
output:
0.5000000000
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3544kb
input:
10000 10 1936 7177 7367 5288 4099 4002 4306 7157 9479 2617 748 261 6057 9605 800 4139 6942 1774 9797 7984
output:
0.1620195081
result:
ok found '0.1620195', expected '0.1620195', error '0.0000000'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3544kb
input:
10000 11 1565 2021 4756 9480 8808 5713 8831 4007 689 8849 3708 4002 7817 1966 4908 1296 536 5911 4943 5818 7696 7058
output:
0.1555705333
result:
ok found '0.1555705', expected '0.1555705', error '0.0000000'
Test #13:
score: 0
Accepted
time: 2ms
memory: 3680kb
input:
10000 3 3973 3433 1499 9465 9827 2865
output:
0.3336467643
result:
ok found '0.3336468', expected '0.3336468', error '0.0000000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
10000 4 1192 5612 4993 4980 6871 464 8012 9032
output:
0.2529493753
result:
ok found '0.2529494', expected '0.2529494', error '0.0000000'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
10000 5 5394 1945 2122 3421 2302 7573 6642 7861 8122 4335
output:
0.2284404407
result:
ok found '0.2284404', expected '0.2284404', error '0.0000000'
Test #16:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
10000 6 4562 1211 7899 8180 9390 2001 4776 4906 1289 4598 2982 8356
output:
0.2065604479
result:
ok found '0.2065604', expected '0.2065604', error '0.0000000'
Test #17:
score: 0
Accepted
time: 2ms
memory: 3528kb
input:
10000 7 4707 2821 279 849 9510 9857 7858 1692 2613 5549 7070 5057 2952 8297
output:
0.1943297653
result:
ok found '0.1943298', expected '0.1943298', error '0.0000000'
Test #18:
score: 0
Accepted
time: 2ms
memory: 3688kb
input:
10000 8 8737 940 9223 5124 5390 4821 1855 6574 7355 8859 3454 8630 1787 2872 4508 1716
output:
0.1826088061
result:
ok found '0.1826088', expected '0.1826088', error '0.0000000'
Test #19:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
10000 9 7428 7228 4810 2667 686 8569 1734 4870 5991 4783 1610 1939 8519 5145 8269 577 5063 9277
output:
0.1705187028
result:
ok found '0.1705187', expected '0.1705187', error '0.0000000'
Test #20:
score: 0
Accepted
time: 2ms
memory: 3676kb
input:
10000 10 7940 1843 2890 4497 690 6204 8917 4193 5711 5590 5542 7537 1865 9104 2809 1726 5172 1363 8945 8896
output:
0.1390584304
result:
ok found '0.1390584', expected '0.1390584', error '0.0000000'
Test #21:
score: 0
Accepted
time: 4ms
memory: 3708kb
input:
10000 100 576 6763 8091 9479 4180 5809 2095 2845 7735 594 5592 7607 4322 3991 5192 5906 6120 5721 255 3614 2782 9241 3606 6891 9466 8109 6419 3866 157 8030 4831 2721 6997 126 5844 4650 7082 5464 1598 1857 1870 6427 4353 9708 812 9635 5356 2234 8078 5691 788 2088 2364 5680 9326 4830 4544 1609 9935 63...
output:
0.0263257336
result:
ok found '0.0263257', expected '0.0263257', error '0.0000000'
Test #22:
score: 0
Accepted
time: 2ms
memory: 3684kb
input:
10000 11 1447 8319 5380 1104 9798 321 3761 9990 2712 5702 5405 7085 9044 4112 1253 3950 6179 4216 2922 1937 7948 7344
output:
0.1305235115
result:
ok found '0.1305235', expected '0.1305235', error '0.0000000'
Test #23:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
10000 12 7293 1083 1909 798 8736 7459 2238 5932 260 9992 4201 7893 1660 3770 6703 8610 7784 5087 4995 5174 8976 2394 4580 2155
output:
0.1155761454
result:
ok found '0.1155761', expected '0.1155761', error '0.0000000'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
10000 13 5084 7147 9078 1457 8366 7019 2233 2360 8875 5085 1528 7776 6366 3955 3390 1580 6973 8519 760 4836 3501 5161 6413 625 3197 9209
output:
0.1120467691
result:
ok found '0.1120468', expected '0.1120468', error '0.0000000'
Test #25:
score: 0
Accepted
time: 1ms
memory: 3544kb
input:
10000 14 4533 9004 8155 7396 1962 8825 4508 665 8981 5384 3268 5400 1317 3433 2328 1834 5239 5310 7048 8791 5756 3338 8865 2697 7863 537 693 6890
output:
0.1035664836
result:
ok found '0.1035665', expected '0.1035665', error '0.0000000'
Test #26:
score: 0
Accepted
time: 3ms
memory: 3592kb
input:
10000 16 9024 825 674 6738 5990 1746 4114 3384 7893 8513 9046 7029 6144 5736 9166 4304 1166 3859 6900 3513 3571 681 3407 5687 3990 7972 5852 9129 1799 8850 1413 1513
output:
0.0929695101
result:
ok found '0.0929695', expected '0.0929695', error '0.0000000'
Test #27:
score: 0
Accepted
time: 616ms
memory: 3768kb
input:
10000 1600 8251 3131 6464 944 8924 7410 8793 9795 8033 9172 7583 4863 8489 7861 3271 7771 9160 6531 4918 3741 1468 2378 6512 6210 7452 372 6421 2742 8753 6574 6445 1531 7801 6078 5773 7188 8749 1934 3737 6735 2074 5147 1307 2226 7084 1743 7082 7997 8646 3328 1215 2744 1957 6024 2413 7526 7777 6861 5...
output:
0.0104111580
result:
ok found '0.0104112', expected '0.0104112', error '0.0000000'
Test #28:
score: 0
Accepted
time: 1ms
memory: 3544kb
input:
10000 17 4067 6307 8803 2661 7786 8524 6791 5924 5804 9192 5522 3664 930 6283 9030 7239 5534 768 7575 1385 1742 8219 772 3876 3059 939 3559 4259 3413 9044 1184 1648 9246 4866
output:
0.0884403361
result:
ok found '0.0884403', expected '0.0884403', error '0.0000000'
Test #29:
score: 0
Accepted
time: 3ms
memory: 3688kb
input:
10000 25 3882 8972 6740 1455 5544 9436 8861 9126 3698 4810 7080 3582 6063 6756 4720 2811 5222 602 1986 8783 1675 7483 454 2576 9462 7215 8486 829 1167 1017 1711 4896 2748 3349 5834 4621 814 6398 7509 6145 9197 2585 3900 6920 2737 648 8712 4943 6874 8469
output:
0.0683810427
result:
ok found '0.0683810', expected '0.0683810', error '0.0000000'
Test #30:
score: 0
Accepted
time: 2ms
memory: 3752kb
input:
10000 3 2851 4542 6597 8772 6716 2370
output:
0.3334334282
result:
ok found '0.3334334', expected '0.3334334', error '0.0000000'
Test #31:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
10000 4 9029 9615 989 402 7024 3559 2974 6440
output:
0.2501582221
result:
ok found '0.2501582', expected '0.2501582', error '0.0000000'
Test #32:
score: 0
Accepted
time: 64ms
memory: 3548kb
input:
10000 400 6224 8176 648 3080 7006 3557 1590 9310 4262 2472 8217 4647 583 1810 757 1109 5110 9801 1186 284 7393 283 7483 2037 126 7856 6992 3080 8548 9436 2496 6059 6626 2674 5117 1435 2092 6882 2818 4020 4972 544 4843 5794 371 1460 6327 7003 7341 7040 1011 1226 4670 1545 4368 3523 6612 2903 1028 529...
output:
0.0139303603
result:
ok found '0.0139304', expected '0.0139304', error '0.0000000'
Test #33:
score: 0
Accepted
time: 1ms
memory: 3696kb
input:
10000 5 2023 5815 8240 6536 4980 8050 7164 2404 2682 1899
output:
0.2160249638
result:
ok found '0.2160250', expected '0.2160250', error '0.0000000'
Test #34:
score: 0
Accepted
time: 4ms
memory: 3536kb
input:
10000 6 6859 1228 1372 7389 8870 5447 6027 8884 4969 4893 1550 1861
output:
0.1884456284
result:
ok found '0.1884456', expected '0.1884456', error '0.0000000'
Test #35:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
10000 7 7417 1413 7697 6959 4285 6615 3864 3810 8683 3887 1093 9810 916 2679
output:
0.1886137602
result:
ok found '0.1886138', expected '0.1886138', error '0.0000000'
Test #36:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
10000 8 8471 2543 3116 1981 8415 6324 1633 9296 1561 4311 6726 8893 4337 5852 6163 1314
output:
0.1571311321
result:
ok found '0.1571311', expected '0.1571311', error '0.0000000'
Test #37:
score: 0
Accepted
time: 2ms
memory: 3540kb
input:
10000 9 2943 8746 1227 6706 6569 1156 1546 3564 6234 8512 3308 1663 5767 4982 8316 6957 8996 2578
output:
0.1400285297
result:
ok found '0.1400285', expected '0.1400285', error '0.0000000'
Test #38:
score: 0
Accepted
time: 2ms
memory: 3684kb
input:
10000 10 4914 1879 1125 4192 1718 887 1737 7176 3576 8574 9358 7418 5129 4866 7987 4367 7809 1635 6695 8870
output:
0.1290906165
result:
ok found '0.1290906', expected '0.1290906', error '0.0000000'
Test #39:
score: 0
Accepted
time: 2ms
memory: 3684kb
input:
10000 11 3602 8803 8229 7912 1207 5152 6423 8673 6297 5090 7497 2055 5145 1051 3421 3728 1029 569 9151 4483 2167 7373
output:
0.1261753905
result:
ok found '0.1261754', expected '0.1261754', error '0.0000000'
Test #40:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
10000 12 8604 906 8094 8042 5125 1290 8874 5898 1252 1512 3101 6572 611 8533 1413 4539 5563 6092 7755 3610 5149 9454 4361 3725
output:
0.1203380224
result:
ok found '0.1203380', expected '0.1203380', error '0.0000000'
Test #41:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
10000 13 944 2026 6943 6462 4559 4363 9479 6612 8302 3748 4492 8765 7974 2021 7516 9098 1224 4642 1184 8667 3633 6549 5591 1252 2865 643
output:
0.1128698095
result:
ok found '0.1128698', expected '0.1128698', error '0.0000000'
Test #42:
score: 0
Accepted
time: 2ms
memory: 3692kb
input:
10000 14 4190 9346 4131 6402 9305 4324 7474 5205 9798 9028 861 6243 4702 4625 1988 3619 8169 2089 3684 1740 1498 8824 6505 881 6679 7473 819 778
output:
0.1052989177
result:
ok found '0.1052989', expected '0.1052989', error '0.0000000'
Test #43:
score: 0
Accepted
time: 2ms
memory: 3684kb
input:
10000 15 9451 9229 4692 938 6278 8273 6991 6344 2434 6752 976 4962 7266 1210 4281 8342 2382 1523 1390 8830 8812 5048 1535 2396 8990 2324 5889 4156 3829 4738
output:
0.0993953958
result:
ok found '0.0993954', expected '0.0993954', error '0.0000000'
Test #44:
score: 0
Accepted
time: 2ms
memory: 3536kb
input:
10000 16 7661 5322 5592 9141 1790 8096 1275 878 824 3551 3392 4402 8557 1236 6151 887 8868 7449 7778 8720 3294 8854 6069 3517 1010 6119 4978 5947 9241 3227 3814 1927
output:
0.0933180273
result:
ok found '0.0933180', expected '0.0933180', error '0.0000000'
Test #45:
score: 0
Accepted
time: 637ms
memory: 3680kb
input:
10000 1600 465 637 1555 7510 9878 2817 4134 8079 7390 3118 5930 4498 4862 811 8287 2925 8265 7684 9460 7810 6185 6701 8553 8988 4672 9527 978 1875 9024 6021 5027 901 7098 350 6182 967 1345 306 8679 8266 4088 738 9151 8094 6289 3654 3205 8134 9440 7363 895 5875 206 7309 7391 1784 102 9335 6156 4028 2...
output:
0.0066145448
result:
ok found '0.0066145', expected '0.0066145', error '0.0000000'
Test #46:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
10000 17 6079 920 9000 8855 2072 5158 6294 8486 6910 3912 6554 6729 1766 8688 2127 3210 3854 9187 8524 5896 1122 775 9318 3047 729 6970 3913 6281 8636 635 5005 3840 3795 1764
output:
0.0901453824
result:
ok found '0.0901454', expected '0.0901454', error '0.0000000'
Test #47:
score: 0
Accepted
time: 2ms
memory: 3544kb
input:
10000 3 6520 8727 6721 3621 1261 2708
output:
0.3333479248
result:
ok found '0.3333479', expected '0.3333479', error '0.0000000'
Test #48:
score: 0
Accepted
time: 2240ms
memory: 3856kb
input:
10000 3000 2995 817 6811 8777 2212 9777 2530 4530 9285 1516 1163 3396 3135 4216 6027 4923 9755 9237 1842 5438 2530 1410 7106 6586 1675 3162 2277 9377 6914 7784 568 7221 4053 2846 1313 4810 2655 4999 5787 1376 4461 2685 5660 6273 1147 8389 8187 1469 5566 290 4930 3291 1720 8868 1854 5655 381 1368 789...
output:
0.0047799918
result:
ok found '0.0047800', expected '0.0047800', error '0.0000000'
Test #49:
score: 0
Accepted
time: 2ms
memory: 3680kb
input:
10000 4 884 5632 9116 4368 5144 7565 4856 2435
output:
0.2500340845
result:
ok found '0.2500341', expected '0.2500341', error '0.0000000'
Test #50:
score: 0
Accepted
time: 39ms
memory: 3564kb
input:
10000 400 6719 9233 5750 1533 4370 4206 868 2914 2657 1959 9406 7427 4569 7465 2838 6861 904 1847 5489 2972 6305 7290 9338 3886 4573 3891 9758 8741 5887 9069 6784 1348 2097 7148 9653 9709 1642 5137 4591 288 2590 760 9381 6127 8621 1238 3668 3612 7629 4537 736 8177 1121 2740 6109 9474 1407 6125 3816 ...
output:
0.0119717564
result:
ok found '0.0119718', expected '0.0119718', error '0.0000000'
Test #51:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
10000 5 1191 9956 8235 2313 3750 4999 3019 1405 7426 7207
output:
0.2250516240
result:
ok found '0.2250516', expected '0.2250516', error '0.0000000'
Test #52:
score: 0
Accepted
time: 2ms
memory: 3760kb
input:
10000 6 8183 6874 7968 2915 2001 6961 4813 1856 1846 3259 5310 8197
output:
0.1918894381
result:
ok found '0.1918894', expected '0.1918894', error '0.0000000'
Test #53:
score: 0
Accepted
time: 2ms
memory: 3544kb
input:
10000 8 2464 9873 3838 1955 1501 6836 6177 3794 1895 3013 8391 6549 5708 7258 9697 620
output:
0.1690403940
result:
ok found '0.1690404', expected '0.1690404', error '0.0000000'
Test #54:
score: 0
Accepted
time: 154ms
memory: 3800kb
input:
10000 800 7013 2607 1392 6631 1255 2302 6621 7697 9687 2565 8367 6983 1565 3281 9486 5509 8452 8369 7566 2264 9302 9275 4816 8422 2753 2251 6125 3563 6656 4234 6586 7992 4996 1958 9799 3651 4945 1214 1242 5884 2232 9957 1018 3146 7293 5198 9240 8003 9526 205 4177 6497 2689 7772 8212 4778 8872 771 75...
output:
0.0089288885
result:
ok found '0.0089289', expected '0.0089289', error '0.0000000'
Test #55:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
10000 9 5076 8596 8900 1376 4644 5624 1460 4511 8295 8127 1201 8051 5414 1273 8084 4974 2552 2243
output:
0.1425113525
result:
ok found '0.1425114', expected '0.1425114', error '0.0000000'
Test #56:
score: 0
Accepted
time: 1745ms
memory: 3836kb
input:
9856 2965 64 64 64 384 64 576 64 896 64 1088 64 1408 64 1600 64 1920 64 2112 64 2432 64 2624 64 2944 64 3136 64 3456 64 3648 64 3968 64 4160 64 4480 64 4672 64 4992 64 5184 64 5504 64 5696 64 6016 64 6208 64 6528 64 6720 64 7040 64 7232 64 7552 64 7744 64 8064 64 8256 64 8576 64 8768 64 9088 64 9280...
output:
0.0129826329
result:
ok found '0.0129826', expected '0.0129826', error '0.0000000'
Test #57:
score: 0
Accepted
time: 3ms
memory: 3540kb
input:
1000 1 601 439
output:
0.6496780000
result:
ok found '0.6496780', expected '0.6496780', error '0.0000000'
Test #58:
score: 0
Accepted
time: 2ms
memory: 3544kb
input:
1000 1 838 390
output:
0.8736400000
result:
ok found '0.8736400', expected '0.8736400', error '0.0000000'
Test #59:
score: 0
Accepted
time: 2ms
memory: 3684kb
input:
1000 1 791 976
output:
0.9899680000
result:
ok found '0.9899680', expected '0.9899680', error '0.0000000'
Test #60:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
10000 1 5000 5000
output:
0.5000000000
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #61:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
10 10 2 7 8 9 5 9 9 2 8 4 9 8 5 7 4 3 7 4 7 3
output:
0.4000000000
result:
ok found '0.4000000', expected '0.4000000', error '0.0000000'
Test #62:
score: 0
Accepted
time: 4ms
memory: 3668kb
input:
100 100 28 17 61 41 20 56 45 82 17 31 96 94 21 2 71 80 2 39 34 37 20 38 47 57 33 35 21 14 25 1 25 69 43 49 13 63 10 63 31 25 17 35 48 30 46 80 96 20 49 36 56 63 23 82 89 37 93 39 98 11 77 3 69 87 19 74 74 59 80 27 13 2 17 52 67 13 96 73 34 36 16 7 4 88 56 83 48 71 37 45 59 17 31 67 76 71 40 14 66 24...
output:
0.1148275862
result:
ok found '0.1148276', expected '0.1148276', error '0.0000000'
Test #63:
score: 0
Accepted
time: 240ms
memory: 3588kb
input:
1000 1000 894 23 280 493 664 873 275 213 46 499 171 479 259 307 743 525 330 210 920 458 64 69 986 569 90 777 915 375 15 226 363 253 809 179 307 855 836 348 611 110 896 400 264 628 393 751 803 61 304 934 672 867 947 286 174 641 93 117 81 393 566 393 264 774 48 973 321 399 1 428 721 958 855 322 536 58...
output:
0.0379133574
result:
ok found '0.0379134', expected '0.0379134', error '0.0000000'
Test #64:
score: 0
Accepted
time: 2235ms
memory: 3700kb
input:
10000 3000 2542 661 3834 3552 2674 1156 3362 911 6607 7777 6132 5523 3045 2361 2840 7965 7575 7359 4646 9944 9845 8736 9933 1214 3293 6526 68 2896 5837 458 2160 5504 9111 819 9713 6627 250 7146 5262 7084 3390 1271 181 2972 9397 5366 8150 7621 8073 7255 8861 5396 7210 7119 4467 9068 5088 1607 9062 49...
output:
0.0106693734
result:
ok found '0.0106694', expected '0.0106694', error '0.0000000'
Test #65:
score: 0
Accepted
time: 2253ms
memory: 3920kb
input:
10000 3000 1579 4794 6416 2391 1158 9080 3772 9132 7869 6924 3312 5966 7990 6312 8860 9575 6152 8142 8957 4426 985 9430 1998 1274 9663 9809 5052 2770 298 2867 883 6145 1189 5147 9510 4303 792 1658 2923 9232 385 7694 6869 1857 9776 2548 2108 9454 6130 4475 5636 9569 271 1287 9324 7433 3260 4664 7342 ...
output:
0.0097183157
result:
ok found '0.0097183', expected '0.0097183', error '0.0000000'
Test #66:
score: 0
Accepted
time: 2271ms
memory: 3920kb
input:
10000 3000 8397 794 6789 7598 2276 7483 3110 63 7915 2160 7876 3125 7006 8098 5431 9731 2497 5969 6754 972 3350 8665 4048 9545 4294 3182 7960 5593 6904 811 3998 1055 1539 3135 4040 7432 5379 4613 728 8690 3945 7320 812 2478 2613 5811 8362 9712 477 5211 1964 3948 5854 7828 3806 8283 1164 4362 6165 11...
output:
0.0148165640
result:
ok found '0.0148166', expected '0.0148166', error '0.0000000'
Test #67:
score: 0
Accepted
time: 1ms
memory: 3696kb
input:
1000 2 116 287 880 894
output:
0.5920890052
result:
ok found '0.5920890', expected '0.5920890', error '0.0000000'
Test #68:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
1000 2 900 316 150 974
output:
0.6605780750
result:
ok found '0.6605781', expected '0.6605781', error '0.0000000'
Test #69:
score: 0
Accepted
time: 2ms
memory: 3680kb
input:
1000 2 902 455 801 703
output:
0.8743160372
result:
ok found '0.8743160', expected '0.8743160', error '0.0000000'
Test #70:
score: 0
Accepted
time: 2ms
memory: 3536kb
input:
997 2 934 8 933 7
output:
0.9989859247
result:
ok found '0.9989859', expected '0.9989859', error '0.0000000'