QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#227170 | #7192. Intersection | PPP# | AC ✓ | 524ms | 62120kb | C++17 | 5.7kb | 2023-10-27 00:30:27 | 2023-10-27 00:30:28 |
Judging History
answer
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef double ld;
struct pt{
ld x, y;
int id;
};
int n, m;
const int maxN = 2e5 + 10;
ll a[maxN], b[maxN], c[maxN];
bool bad[maxN];
int x[maxN], y[maxN];
ld area(pt a, pt b, pt c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
const ld eps = 1e-9;
vector<pt> convexHull(vector<pt>& pts) {
sort(pts.begin(), pts.end(), [&](const pt &a, const pt &b) {
return a.x + eps < b.x || (fabsl(a.x - b.x) < eps && a.y + eps < b.y);
});
vector<pt> npts;
for (auto& it : pts) {
if (!npts.empty() && fabsl(it.x - npts.back().x) < eps && fabsl(it.y - npts.back().y) < eps) {
continue;
}
npts.emplace_back(it);
}
pts = npts;
if (pts.size() < 3) {
return pts;
}
pt pUp = pts.front(), pDown = pts.back();
vector<pt> up{pUp}, down{pUp};
for (size_t i = 1; i < pts.size(); ++i) {
if (i == pts.size() - 1 || area(pUp, pts[i], pDown) < -eps) {
while (up.size() >= 2 &&
area(up[up.size()-2], up.back(), pts[i]) > -eps) {
up.pop_back();
}
up.push_back(pts[i]);
}
if (i == pts.size() - 1 || area(pUp, pts[i], pDown) > eps) {
while (down.size() >= 2 &&
area(down[down.size()-2], down.back(), pts[i]) < eps) {
down.pop_back();
}
down.push_back(pts[i]);
}
}
assert(up.size() >= 2);
for (size_t i = up.size() - 2; i > 0; --i) {
down.push_back(up[i]);
}
return down;
}
ll det(ll a11, ll a12, ll a21, ll a22) {
return a11 * a22 - a21 * a12;
}
pair<pair<int,int>, pair<int,int>> val_l[maxN];
pair<pair<int,int>, pair<int,int>> val_r[maxN];
pt L[maxN], R[maxN];
bool cmp(pair<int, int> a, pair <int, int> b) {
return (1LL * a.first * b.second < 1LL * a.second * b.first);
}
void upd(int where, ll DX, ll DY, ll D) {
pair<pair<int,int>, pair<int,int>> we = make_pair(make_pair(DX, D), make_pair(DY, D));
if (val_l[where].first.second == 0) {
val_l[where] = we;
val_r[where] = we;
L[where] = {(ld)DX / D, (ld)DY / D, -1};
R[where] = {(ld)DX / D, (ld)DY / D, -1};
return;
}
if (cmp(we.first, val_l[where].first) || (!cmp(val_l[where].first, we.first) && cmp(we.second, val_l[where].second))) {
val_l[where] = we;
L[where] = {(ld)DX / D, (ld)DY / D, -1};
}
if (cmp(val_r[where].first, we.first) || (!cmp(we.first, val_r[where].first) && cmp(val_r[where].second, we.second))) {
val_r[where] = we;
R[where] = {(ld)DX / D, (ld)DY / D, -1};
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef DEBUG
freopen("input.txt", "r", stdin);
#endif
cin >> n >> m;
if (m >= (1LL * n * (n - 1)) / 2 - 1) {
cout << fixed << setprecision(12) << 0;
return 0;
}
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i] >> c[i];
if (b[i] == 0) {
bad[i] = true;
}
}
map<pair<int,int>,int> mp;
for (int i = 1; i <= m; i++) {
cin >> x[i] >> y[i];
assert(!mp.count({x[i], y[i]}));
mp[{x[i], y[i]}] = true;
mp[{y[i], x[i]}] = true;
bad[x[i]] = true;
bad[y[i]] = true;
}
vector<pt> ch;
for (int i = 1; i <= n; i++) {
if (bad[i]) continue;
pt f;
f.x = (ld)-a[i] / b[i];
f.y = (ld)c[i] / b[i];
f.id = i;
ch.emplace_back(f);
}
vector<pt> cand;
sort(ch.begin(), ch.end(), [&](pt& a, pt& b) {
return a.x < b.x;
});
auto add = [&](int x, int y) {
ll D = det(a[x], b[x], a[y], b[y]);
ll DX = det(c[x], b[x], c[y], b[y]);
ll DY = det(a[x], c[x], a[y], c[y]);
assert(D != 0);
if (D < 0) {
D *= -1;
DX *= -1;
DY *= -1;
}
upd(x, DX, DY, D);
upd(y, DX, DY, D);
};
for (int x = 0; x < 2; x++) {
for (int sgn = -1; sgn <= 1; sgn += 2) {
vector<pt> cur;
for (auto t : ch) {
while (cur.size() >= 2 && (cur[cur.size() - 2].x - t.x) * (cur.back().y - t.y)
> (cur[cur.size() - 2].y - t.y) * (cur.back().x - t.x)) {
cur.pop_back();
}
if (!cur.empty()) {
add(cur.back().id, t.id);
}
cur.emplace_back(t);
}
for (auto& it : ch) {
it.y *= -1;
}
}
reverse(ch.begin(), ch.end());
}
for (int i = 1; i <= n; i++) {
if (!bad[i]) continue;
for (int j = 1; j <= n; j++) {
if (mp.count({i, j})) continue;
if (i == j) continue;
add(i, j);
}
}
vector<pt> fin;
for (int i = 1; i <= n; i++) {
if (val_l[i].first.second == 0) continue;
fin.emplace_back(L[i]);
fin.emplace_back(R[i]);
}
fin = convexHull(fin);
ld ans = 0;
for (int z = 0; z < fin.size(); z++) {
ld D = sqrtl((fin[(z + 1) % fin.size()].x - fin[z].x) * (fin[(z + 1) % fin.size()].x - fin[z].x) +
(fin[(z + 1) % fin.size()].y - fin[z].y) * (fin[(z + 1) % fin.size()].y - fin[z].y));
ans += D;
}
cout << fixed << setprecision(12) << ans << '\n';
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11872kb
input:
3 0 1 0 0 0 1 0 1 1 1
output:
3.414213562373
result:
ok found '3.4142136', expected '3.4142136', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 14040kb
input:
3 1 1 0 0 0 1 0 1 1 1 1 2
output:
2.828427124746
result:
ok found '2.8284271', expected '2.8284271', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3540kb
input:
1 0 1 1 1
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 13964kb
input:
4 2 1 2 0 1 3 0 1 4 0 1 1 1 1 2 1 3
output:
4.553245560954
result:
ok found '4.5532456', expected '4.5532456', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 15952kb
input:
10 10 0 8 4 -10 -3 6 -1 9 -7 -8 -10 -10 -4 7 3 -8 -5 -8 9 10 -10 -6 -6 5 7 3 10 -9 -4 -7 10 9 9 4 3 1 7 2 4 7 7 8 6 5 6 1 2 5 3 5
output:
49.779204591735
result:
ok found '49.7792046', expected '49.7792046', error '0.0000000'
Test #6:
score: 0
Accepted
time: 2ms
memory: 13880kb
input:
10 10 -8 -3 3 -4 -3 9 -7 -8 8 5 1 -6 8 -8 6 -9 4 10 0 5 7 -1 -10 10 -4 6 -3 2 -8 -5 8 7 5 8 1 8 2 3 9 10 1 2 7 9 4 1 2 6 4 6
output:
19.653561435354
result:
ok found '19.6535614', expected '19.6535614', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 13872kb
input:
10 10 -3 2 -7 -6 5 -2 7 7 -7 -2 -6 -10 -1 1 1 -10 -4 6 -5 4 -9 -6 -5 3 8 5 -10 -3 10 9 5 10 8 9 5 2 8 3 9 6 4 10 7 2 1 6 3 4 7 1
output:
46.845684098808
result:
ok found '46.8456841', expected '46.8456841', error '0.0000000'
Test #8:
score: 0
Accepted
time: 3ms
memory: 13880kb
input:
10 10 -2 -9 -1 4 5 9 0 -6 7 7 0 -6 -10 3 8 6 5 -1 -8 9 -1 1 4 3 3 1 -1 5 5 -5 2 1 5 4 9 1 1 3 6 1 5 7 10 1 4 3 7 9 7 3
output:
85.692465262721
result:
ok found '85.6924653', expected '85.6924653', error '0.0000000'
Test #9:
score: 0
Accepted
time: 2ms
memory: 14052kb
input:
10 10 6 9 -2 1 9 -6 -7 -2 5 7 -7 -10 -2 -9 4 1 10 -1 4 8 7 6 0 8 -6 -6 -7 10 -1 0 6 1 1 7 6 2 1 9 6 10 9 4 2 3 3 8 10 8 8 9
output:
19.339340020614
result:
ok found '19.3393400', expected '19.3393400', error '0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 13884kb
input:
10 10 -10 -10 9 -5 -4 5 8 5 -5 -1 3 -6 2 10 -10 0 5 0 -4 -1 3 -10 4 -8 2 -1 4 10 2 4 7 3 1 4 5 9 1 2 9 10 5 7 6 8 10 4 8 3 10 7
output:
38.662093930606
result:
ok found '38.6620939', expected '38.6620939', error '0.0000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 15848kb
input:
10 10 3 -1 -9 9 9 -6 1 9 -8 -10 -7 -6 6 -5 -7 -9 1 2 1 -7 -6 6 4 -10 8 6 -10 -2 -9 1 8 4 3 1 3 7 1 6 10 2 3 10 6 8 9 4 2 9 1 5
output:
25.912856124987
result:
ok found '25.9128561', expected '25.9128561', error '0.0000000'
Test #12:
score: 0
Accepted
time: 2ms
memory: 14032kb
input:
10 10 8 5 -6 2 -8 1 -6 -1 -6 5 7 -6 5 -5 -4 -5 -2 10 5 3 -5 -4 -7 3 -8 -6 6 -5 3 -8 3 6 10 5 6 8 5 9 2 4 2 6 9 4 2 3 6 9 10 2
output:
35.299964104203
result:
ok found '35.2999641', expected '35.2999641', error '0.0000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 13880kb
input:
10 10 9 7 0 -8 -4 -10 -8 -3 0 -10 -4 5 -9 -10 -10 10 -4 2 -1 1 10 8 0 8 8 -5 1 1 -4 1 6 9 4 3 8 6 8 3 3 1 10 4 4 9 2 4 1 9 3 5
output:
95.167961596330
result:
ok found '95.1679616', expected '95.1679616', error '0.0000000'
Test #14:
score: 0
Accepted
time: 2ms
memory: 13916kb
input:
10 10 -6 2 -3 6 4 2 -5 -7 1 0 3 5 2 -3 -8 -9 2 -9 1 -2 -1 -10 10 2 -3 8 5 -2 -2 0 8 10 10 3 5 7 5 9 4 9 5 2 6 5 6 8 5 4 1 10
output:
26.719240045470
result:
ok found '26.7192400', expected '26.7192400', error '0.0000000'
Test #15:
score: 0
Accepted
time: 0ms
memory: 16120kb
input:
100 50 6 34 -1 -55 85 -11 33 -76 -79 -23 6 -20 75 48 77 -87 35 -16 -8 -79 -49 3 -2 -8 1 45 35 -27 -79 -77 64 -51 -88 85 6 74 20 -93 -30 63 11 74 76 3 -70 67 39 53 -35 100 -95 -94 53 -85 -22 -6 43 9 -3 -69 -31 -80 55 -93 -70 29 -55 -67 21 51 -96 -6 40 -93 20 94 -54 -22 94 95 0 -48 59 55 100 -40 97 33...
output:
4237.215091379009
result:
ok found '4237.2150914', expected '4237.2150914', error '0.0000000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 14072kb
input:
100 50 37 -66 -18 -83 -83 99 -100 -97 3 -80 91 73 -39 7 24 -33 93 37 -52 -70 -12 96 -24 38 -88 -97 -31 -42 -4 -1 -17 3 57 13 66 31 -26 15 38 91 95 -29 24 10 41 -65 4 68 -23 -41 24 -91 68 -56 -21 -30 75 53 -68 -14 55 -15 -16 56 -92 46 -35 -81 -86 -38 20 25 63 -73 87 -62 19 20 10 62 44 91 -97 -20 30 8...
output:
14562.176257060317
result:
ok found '14562.1762571', expected '14562.1762571', error '0.0000000'
Test #17:
score: 0
Accepted
time: 0ms
memory: 14068kb
input:
100 50 44 10 -8 65 51 8 -33 -18 83 -10 0 -35 49 41 71 97 50 -35 5 16 -51 -88 54 84 -51 -38 27 -81 -54 75 -23 32 0 42 -74 13 3 46 6 17 -21 -5 -26 -84 26 -72 -29 58 -87 -57 42 14 -17 73 80 -79 31 -79 -33 -34 -35 -77 -12 4 -39 63 -90 4 -93 -51 -66 55 -15 48 -47 58 -34 61 -75 30 -37 54 48 -97 -39 -65 -2...
output:
3709.671025193868
result:
ok found '3709.6710252', expected '3709.6710252', error '0.0000000'
Test #18:
score: 0
Accepted
time: 0ms
memory: 13892kb
input:
100 50 75 -15 76 -88 -42 -82 -65 61 63 -67 85 58 -39 0 -82 -50 -68 -82 -14 -70 32 -46 -39 21 -40 -96 21 -50 -28 86 -56 -30 -14 -31 -43 -47 49 45 39 94 -78 23 -64 98 38 47 50 -97 62 -84 -1 1 6 -1 -13 -34 3 -55 -49 -38 -8 53 39 -96 56 90 -100 -66 50 -15 -94 68 -55 -98 -86 -99 -84 99 -93 -8 17 -72 -7 8...
output:
9554.846640424541
result:
ok found '9554.8466404', expected '9554.8466404', error '0.0000000'
Test #19:
score: 0
Accepted
time: 0ms
memory: 16104kb
input:
100 50 -94 86 -16 -41 91 28 3 -61 -82 2 -31 51 49 -66 -35 4 -11 -29 95 85 -78 23 10 0 -3 -45 -82 65 -4 -75 67 15 -87 100 47 52 -90 -16 17 97 -77 93 -28 30 47 92 4 -38 -38 88 80 -5 15 -71 7 -25 -81 -91 -62 -76 37 27 -79 1 92 22 -25 -25 -31 21 90 15 29 88 12 -53 62 -58 -67 67 -49 30 60 53 -52 -66 -12 ...
output:
8547.280268488899
result:
ok found '8547.2802685', expected '8547.2802685', error '0.0000000'
Test #20:
score: 0
Accepted
time: 0ms
memory: 16044kb
input:
100 50 12 61 69 -94 -76 -63 -55 94 100 -55 79 -32 -40 94 13 33 47 -77 52 94 59 40 88 -54 -91 14 52 -50 -29 2 -14 -31 -42 -72 7 34 -62 -84 85 23 7 -8 -4 -64 57 60 -30 52 99 72 -27 -1 -70 -43 -68 -74 -24 79 -27 4 -77 66 -75 -51 -56 39 -80 -65 62 33 4 46 -24 8 79 -33 -66 8 49 35 71 93 4 -23 -20 -15 30 ...
output:
23066.081492891535
result:
ok found '23066.0814929', expected '23066.0814929', error '0.0000000'
Test #21:
score: 0
Accepted
time: 2ms
memory: 13900kb
input:
100 50 44 36 53 54 57 47 -88 -29 80 15 -37 61 48 -73 -40 -13 29 -48 -91 -21 96 57 66 17 46 73 85 11 21 -23 80 98 1 57 -33 91 93 23 -48 -50 67 -10 46 43 -33 54 12 -58 10 32 -9 2 -30 86 -67 -98 -93 22 -92 84 -66 -96 -71 -2 22 56 -35 -80 55 -81 -81 76 -2 28 -30 -89 82 49 66 -97 15 -70 -27 -99 -89 -90 -...
output:
3168.558655251171
result:
ok found '3168.5586553', expected '3168.5586553', error '0.0000000'
Test #22:
score: 0
Accepted
time: 0ms
memory: 13896kb
input:
100 50 75 -64 61 1 -10 -43 -21 -50 -40 59 73 -47 -41 87 7 16 87 -95 41 -37 32 75 45 -39 -17 -68 -56 -3 -4 53 75 -49 46 86 27 -28 -79 55 96 -23 -49 -86 95 50 -48 23 -21 -43 47 16 -91 -94 -14 14 -66 -20 -35 -9 -57 -37 20 -56 -67 46 75 73 86 -94 -52 5 -66 6 20 -52 37 -70 -71 91 -19 72 -66 69 18 26 42 6...
output:
6342.363872994109
result:
ok found '6342.3638730', expected '6342.3638730', error '0.0000000'
Test #23:
score: 0
Accepted
time: 0ms
memory: 13900kb
input:
100 50 82 -89 45 49 23 92 -53 -71 -60 -73 -43 46 47 -79 -46 70 -57 58 98 48 68 -33 23 -93 95 -9 78 82 72 29 95 81 91 39 -12 55 75 -14 -37 -96 10 12 -56 -44 63 17 -56 -54 83 -25 28 -91 -99 -58 61 -69 97 -66 -22 -82 -95 7 63 95 -48 15 -70 -9 -59 -8 74 -65 -57 69 4 -25 -98 31 97 64 79 32 -38 50 -27 10 ...
output:
5068.374553841857
result:
ok found '5068.3745538', expected '5068.3745538', error '0.0000000'
Test #24:
score: 0
Accepted
time: 0ms
memory: 13988kb
input:
100 50 37 76 60 -84 -10 66 -69 64 -95 35 -92 2 78 -64 76 43 -40 -40 69 73 -27 -20 2 -25 -17 -41 64 -6 45 22 61 8 2 -2 28 -33 59 -53 -10 46 -9 13 17 -48 -14 -18 -75 95 -43 -72 -67 17 -86 -68 95 -80 49 -73 -34 -51 64 -98 13 61 -43 11 -70 -54 61 -13 -47 -88 20 65 -76 -65 -90 89 16 -48 -73 -39 72 64 91 ...
output:
5608.177883918240
result:
ok found '5608.1778839', expected '5608.1778839', error '0.0000000'
Test #25:
score: 0
Accepted
time: 3ms
memory: 13984kb
input:
100 50 2371 -2182 4649 -7045 1625 6370 105 7051 -9889 8094 -378 -5091 3473 1211 776 305 -1104 3821 -6004 -3747 3096 -2940 3883 -2452 4468 8364 7278 -6246 -6010 3529 -1593 -2340 -2959 -4650 3229 -7593 2254 -2797 -7043 -5324 440 -6424 3915 1603 8567 -8255 -1989 -172 -178 6139 -2212 2046 -5614 1102 876...
output:
27472.060887955427
result:
ok found '27472.0608880', expected '27472.0608880', error '0.0000000'
Test #26:
score: 0
Accepted
time: 3ms
memory: 13996kb
input:
100 50 7295 -7151 8895 2840 -7771 4287 9596 629 7734 4640 4998 -2724 -7303 3508 -8632 5689 5745 -3696 -2324 2551 736 -279 5065 -9364 -6120 6689 2325 6218 -3971 9553 9311 6964 6866 -5681 -6294 -8546 3295 9711 3890 -2597 -7660 6808 3862 -5304 8925 -652 8281 829 1161 -3429 3647 -9674 3712 -8684 9818 79...
output:
17411.293822742751
result:
ok found '17411.2938227', expected '17411.2938227', error '0.0000000'
Test #27:
score: 0
Accepted
time: 0ms
memory: 13828kb
input:
100 50 1920 -9858 582 5283 2833 9645 1346 -5793 175 -1670 -9627 9347 6507 5806 -2624 -8927 5151 8787 8798 4263 636 9824 6248 8906 3294 7275 7671 -8760 5510 8136 9917 3708 4131 -6712 -8374 -7238 7193 -5224 2265 9832 6503 -9665 -3633 -9950 7022 6950 3666 1830 -2086 -438 2063 -8836 5596 6712 -1688 -528...
output:
14706.563250841416
result:
ok found '14706.5632508', expected '14706.5632508', error '0.0000000'
Test #28:
score: 0
Accepted
time: 3ms
memory: 13932kb
input:
100 50 -598 -9710 -2614 7727 -6564 120 539 -4773 -9645 2318 -4251 6597 -9387 -4456 528 9016 -2884 1269 2180 5975 536 -74 -2867 1995 5265 5600 2718 6560 7550 -3579 820 -6989 8839 -302 4961 -3074 8234 -9861 -6803 2261 -1596 3567 8873 -7154 -5179 1994 3638 -6871 -746 -2564 480 -555 7480 -5335 -2896 144...
output:
17290.181526015695
result:
ok found '17290.1815260', expected '17290.1815260', error '0.0000000'
Test #29:
score: 0
Accepted
time: 3ms
memory: 13824kb
input:
100 50 4326 5322 9074 -2389 4041 5478 -268 8807 2798 -3992 -9173 -1333 -3019 5283 -3762 -3339 6821 4049 -6698 -4872 -9267 2587 -1684 -7178 4975 3925 -9677 -977 -2970 -4996 -8276 2315 -1337 -8775 2880 5675 -7869 2647 -6168 4988 2863 -3202 8820 8201 -7083 -7548 -976 1572 5710 427 6338 284 9364 -7679 -...
output:
16111.661143897069
result:
ok found '16111.6611439', expected '16111.6611439', error '0.0000000'
Test #30:
score: 0
Accepted
time: 0ms
memory: 13988kb
input:
100 50 -8490 2615 -6681 55 -5356 -6308 -1076 5241 -7022 -4 -3797 1034 1089 -4979 9687 2045 -6331 -3468 -3018 -3160 5518 -7311 -3357 -6647 -5613 -8048 3111 -8514 -8373 1029 -7670 1321 -4071 491 -6642 -2720 -6828 -4846 -7793 -2584 -5236 -9972 1325 1294 717 7496 9294 5429 -2654 1157 4754 8565 8392 -716...
output:
7217.032702502401
result:
ok found '7217.0327025', expected '7217.0327025', error '0.0000000'
Test #31:
score: 0
Accepted
time: 0ms
memory: 13936kb
input:
100 50 3876 -9796 -9877 2498 5248 -8391 973 6261 5420 -3458 9021 3402 7457 -2682 5397 -12 -6925 9015 8104 -1448 5418 2793 -9616 -6117 3801 2837 -1842 6806 1109 7053 3234 -9377 5754 6902 1576 -1412 6773 -7222 3140 143 -8219 3260 -6170 4090 -1186 -4902 1824 -6129 -8756 4148 910 -3155 -9725 -9511 -1997...
output:
9104.550466250830
result:
ok found '9104.5504663', expected '9104.5504663', error '0.0000000'
Test #32:
score: 0
Accepted
time: 3ms
memory: 13896kb
input:
100 50 8800 7497 -8487 4942 -4149 -3033 166 -161 -4400 -2326 -5604 2913 -8437 -385 1107 7633 2780 1497 -775 7706 5318 5454 -8433 4711 5772 -1694 -3938 -731 3148 -4662 3840 7369 -7278 5870 -7946 -2365 -1889 -4417 -5927 -7428 5944 -3510 -6223 -556 6613 -4741 4651 7432 -4561 -5420 -674 7386 -7841 5885 ...
output:
30857.605318652342
result:
ok found '30857.6053187', expected '30857.6053187', error '0.0000000'
Test #33:
score: 0
Accepted
time: 2ms
memory: 13940kb
input:
100 50 -4017 2529 -4241 2268 6456 -5116 -8084 -6582 -4516 -5780 -228 -7278 -2069 9354 -5444 5576 2187 -3164 -7393 -3141 -4485 2998 9895 -2200 7743 -3369 -8891 4291 -7372 -6079 -5257 9231 -2570 -2603 2532 -8499 -847 8091 -7553 -7557 -2155 2280 6283 2240 4710 -9697 7479 6172 -3222 5013 -2258 8225 -595...
output:
15176.391148249131
result:
ok found '15176.3911482', expected '15176.3911482', error '0.0000000'
Test #34:
score: 0
Accepted
time: 0ms
memory: 13900kb
input:
100 50 8754 888 -381 -3542 4310 -2292 -1678 -1041 -8367 -4583 -280 -2144 4349 -6430 -3203 -6746 1427 -2288 -5786 -605 3073 -4280 -8381 1800 4489 4959 -4128 8166 -9421 540 -7865 -2658 -1186 -1960 -6268 -1822 -6780 -3314 -8672 -9551 9512 7396 -5115 552 659 9107 -3752 -4072 2847 -6362 -8203 2639 9837 2...
output:
5686.291302671647
result:
ok found '5686.2913027', expected '5686.2913027', error '0.0000000'
Test #35:
score: 0
Accepted
time: 15ms
memory: 14420kb
input:
5000 50 5700 7391 -765 6182 955 4789 2738 3522 -9511 -9375 8053 6271 7210 -4184 5024 -6202 7822 5607 -4541 6422 -3391 -3883 -5790 -8937 9452 -9034 -8442 -3437 -9430 6958 -1807 7162 7510 -8508 1073 4353 -2025 -6727 -6673 7638 -2409 -3032 -4418 -2971 7057 -4730 -3181 9300 3262 -6125 5994 -9459 -3396 3...
output:
38569741.685099132359
result:
ok found '38569741.6850991', expected '38569741.6850991', error '0.0000000'
Test #36:
score: 0
Accepted
time: 11ms
memory: 16380kb
input:
5000 50 -6116 -6942 -5183 -9931 440 -7353 9096 -9737 -370 -6353 -3747 2157 -9089 763 7237 -2700 -1190 -9533 168 6399 47 2641 4718 8573 9428 -805 -9795 -846 -7008 -4909 -9878 -4863 632 -5862 3295 -867 79 3495 -6449 -8160 -9763 -9564 -3826 -5342 -752 457 -8157 8392 3571 -386 4952 -9756 -1075 -6942 -38...
output:
32054994.080926571041
result:
ok found '32054994.0809266', expected '32054994.0809266', error '0.0000000'
Test #37:
score: 0
Accepted
time: 11ms
memory: 14400kb
input:
5000 50 7185 6167 2959 -6042 -75 -1755 -1692 -734 8770 -475 -2989 -1957 4317 -3993 9450 8243 9798 -2411 2616 -6184 6341 -7981 -9360 -4215 -3154 -5136 8853 4601 -4586 7810 4908 -7185 -9103 -7802 -9897 -1501 2184 8537 1217 -9074 2884 -5797 -6090 -271 -1119 2787 9723 -2219 -6419 -4945 1053 -7196 1246 7...
output:
22807058.402091726661
result:
ok found '22807058.4020917', expected '22807058.4020917', error '0.0000000'
Test #38:
score: 0
Accepted
time: 11ms
memory: 14412kb
input:
5000 50 -4631 1537 8244 -5010 9709 6104 79 6008 -2091 285 -7347 1371 8020 8396 4221 -814 786 2450 7324 -3946 75 5985 -8555 -6706 9381 3093 57 -2511 -4425 5645 1953 790 -6279 7404 -233 -9577 -3154 1019 1440 -7727 -6731 7673 -8355 -2642 8217 -2324 4747 -3127 -6110 794 10 -51 3566 -3595 -7346 1001 7597...
output:
12844986.777912668884
result:
ok found '12844986.7779127', expected '12844986.7779127', error '0.0000000'
Test #39:
score: 0
Accepted
time: 11ms
memory: 16384kb
input:
5000 50 8671 -5354 3826 -1122 9194 -3182 9292 5308 -393 -4135 -6588 6961 1424 3640 6434 -7610 -5371 -131 2330 3472 -6190 5066 7071 506 -3201 -1238 9002 -7362 -2004 -9078 -3262 -6649 -5716 -4834 -867 2347 -8491 -3643 9106 -3524 5916 -1120 -321 2429 409 2863 2627 6263 -3541 6533 8670 -347 5887 -1921 -...
output:
34389828.764920994639
result:
ok found '34389828.7649210', expected '34389828.7649210', error '0.0000000'
Test #40:
score: 0
Accepted
time: 11ms
memory: 14492kb
input:
5000 50 9413 -2542 9112 2767 1237 -5026 -1495 1753 8747 9185 9054 2847 5127 6326 -3912 -4109 5617 4730 -5520 3449 7546 -5555 7876 -1984 -3225 6991 206 5527 -7024 3641 1226 1327 4551 -2187 8798 1713 -6387 8841 -3229 8121 -1438 2647 9974 58 9745 -2249 -2349 -4348 6471 -5468 185 2212 8207 9455 1731 -80...
output:
30491514.423866085708
result:
ok found '30491514.4238661', expected '30491514.4238661', error '0.0000000'
Test #41:
score: 0
Accepted
time: 11ms
memory: 14424kb
input:
5000 50 -2403 3125 4694 6655 3578 2833 -2580 1053 -2114 4764 9813 -1267 -8910 -1286 562 6835 4047 9591 9487 3425 1281 8410 -6202 -9656 -3248 2660 -8589 -9027 2840 -8227 -3989 -996 -9770 3315 -4395 -3507 8277 -6119 9554 -234 -8792 -3885 7710 5129 1936 7524 2972 -5256 6779 271 -858 1915 3086 -8873 -62...
output:
21029309.692938566208
result:
ok found '21029309.6929386', expected '21029309.6929386', error '0.0000000'
Test #42:
score: 0
Accepted
time: 11ms
memory: 16496kb
input:
5000 50 -9102 5937 9979 -2015 3064 8431 -5926 7795 -3272 -1917 5455 2061 -5208 -6041 2775 -2223 -4966 7010 9078 -6897 -4984 7492 4306 -2443 -5533 8033 356 -6436 5262 4492 498 -3318 496 -8923 7530 -4141 -9620 -3339 -2781 -8590 -8704 -118 -4257 2758 3830 2413 -9446 4134 -3210 -4288 7803 -5823 -7153 24...
output:
15405928.875117853284
result:
ok found '15405928.8751179', expected '15405928.8751179', error '0.0000000'
Test #43:
score: 0
Accepted
time: 11ms
memory: 14428kb
input:
5000 50 8785 -8396 5562 1873 2549 -3711 3287 9356 5868 1105 6213 7651 8198 -3355 -7571 3540 -1420 -8130 4084 522 8751 4312 -2331 -4934 -5557 -3740 -998 -989 7683 9770 -4717 4658 3321 6283 4636 -4775 5044 9145 -2557 3055 -3499 -6650 -6521 7829 3463 7599 -4124 -4216 9657 1451 -5799 4178 7727 -5526 -97...
output:
25049192.867981396616
result:
ok found '25049192.8679814', expected '25049192.8679814', error '0.0000000'
Test #44:
score: 0
Accepted
time: 11ms
memory: 14456kb
input:
5000 50 -8659 -367 9256 -9844 -2373 3813 -4517 -9608 -4052 -834 8836 4141 -1746 1316 -6769 7685 3834 -4221 -5187 -9190 4411 -6739 4996 -1483 -376 132 -7570 -4867 -2037 -8354 8053 -9958 -6371 -8120 -1516 -323 -7072 1724 1032 -6926 -2715 -6839 -8533 1769 4059 496 9766 -8389 3303 -7413 1434 -4932 -3279...
output:
34007643.007585346699
result:
ok found '34007643.0075853', expected '34007643.0075853', error '0.0000000'
Test #45:
score: 0
Accepted
time: 491ms
memory: 60244kb
input:
200000 50 -9392 -1129 5331 -3946 7566 -4786 1183 3453 2453 -9135 -656 5601 1997 -6870 -7600 3356 8277 625 3122 336 -5593 7915 -3706 5803 6368 4352 -2915 -6409 -7806 5258 -7127 9826 -7748 6449 -107 -899 2256 4705 -5370 8915 -520 5453 7286 4625 -8148 -3985 2129 8398 6114 1653 3975 -7019 -3757 6743 -23...
output:
685910361.939351797104
result:
ok found '685910361.9393518', expected '685910361.9393518', error '0.0000000'
Test #46:
score: 0
Accepted
time: 518ms
memory: 59944kb
input:
200000 50 3717 -5547 9220 -4460 5722 4427 483 -7408 8331 -8376 4933 -994 4683 -4657 -4098 -2801 5696 -7225 -7200 -5929 3786 1278 -3936 5779 -8261 -4444 9974 -3987 -2529 9746 848 92 7458 -3888 -8183 -6237 2180 -7630 -6283 1561 -9313 3189 -7643 -3184 -5817 3597 4077 -1592 -8148 -9688 -3763 7860 -4940 ...
output:
726192406.563762426376
result:
ok found '726192406.5637624', expected '726192406.5637624', error '0.0000000'
Test #47:
score: 0
Accepted
time: 497ms
memory: 60404kb
input:
200000 50 -913 -9964 549 5323 3878 -4100 7225 -5710 -8649 7266 8261 2709 9630 4998 9106 8187 3115 7781 219 -2491 2868 2084 3277 5756 -32 -5797 5123 5877 2748 4530 -1474 5772 -4780 2920 -8817 -4132 -2482 5153 -2080 4505 4157 3781 9987 6153 -631 8919 -9390 978 -9851 9270 6238 -9820 9293 3261 -3926 669...
output:
801487345.437529206276
result:
ok found '801487345.4375292', expected '801487345.4375292', error '0.0000000'
Test #48:
score: 0
Accepted
time: 497ms
memory: 61112kb
input:
200000 50 4755 -4679 4437 4808 -8264 5114 -3773 -6868 4671 8025 -3294 8672 -7685 -232 49 -825 -2322 -7511 -7247 -8756 -3168 -2292 -6656 -6827 -4363 3147 -1989 8298 8026 9018 -6057 -3963 8164 2287 -4335 -9470 -9999 -7182 9565 -2849 7923 1517 -4943 -1656 -5742 -3499 -7442 1286 5591 -2071 5942 -7500 -1...
output:
841632353.848273873329
result:
ok found '841632353.8482739', expected '841632353.8482739', error '0.0000000'
Test #49:
score: 0
Accepted
time: 524ms
memory: 62120kb
input:
200000 50 7566 -9097 8326 4294 2451 -5674 2969 2272 7693 -3775 34 -7626 -4999 1981 3551 -9838 -4903 -5063 171 -2463 6212 -1487 556 -6851 -8693 -5648 -6840 3278 3600 3803 -8380 -3399 -4073 -8050 -4969 -7365 2484 483 -6233 -2761 -8311 -747 -7314 7680 -3411 1823 -8350 3856 -8671 -3114 -1797 -5179 80 -2...
output:
846720759.614533424377
result:
ok found '846720759.6145334', expected '846720759.6145334', error '0.0000000'
Test #50:
score: 0
Accepted
time: 514ms
memory: 60576kb
input:
200000 50 -6767 -3811 -7787 -5924 -2249 3539 2269 3970 -6431 4425 -4080 5780 -51 4194 -5507 -6292 -42 -354 9851 -8728 176 -8123 -1934 5685 -465 5558 6049 -4003 -3682 848 -404 -575 -8869 -1242 4695 7299 -2178 707 5412 2444 -7400 7287 -2243 7313 1775 4288 8482 4164 6772 -4156 -4354 9701 1754 4318 -379...
output:
952846481.452487468719
result:
ok found '952846481.4524875', expected '952846481.4524875', error '0.0000000'
Test #51:
score: 0
Accepted
time: 508ms
memory: 60712kb
input:
200000 50 8604 -8229 3543 6120 -4093 193 -1287 551 -3409 5184 8951 9482 2635 6407 7698 4697 4819 4354 -2732 5008 9556 -5057 5278 3400 -4795 -5499 -8505 5861 -5846 -4367 -2727 9691 6337 981 9178 9403 -9695 931 -5800 -4910 -3634 5022 -4614 -496 4106 2168 132 -5825 -7490 4504 7908 -538 -6871 -3703 -205...
output:
930555767.898788094521
result:
ok found '930555767.8987881', expected '930555767.8987881', error '0.0000000'
Test #52:
score: 0
Accepted
time: 505ms
memory: 59524kb
input:
200000 50 1713 -2943 7432 5605 -5937 -891 -9429 2249 2469 826 -2604 2887 -4977 8620 -8802 3126 2238 6802 9804 -1257 -3922 8308 -7510 3377 3433 -6852 6645 8282 6873 121 -7310 2813 4397 7789 8544 4066 -4654 1155 -1597 7737 9836 -4684 457 1398 -1005 -2808 -3037 -5517 7952 3461 7612 -5659 -5198 836 -542...
output:
867511792.595178127289
result:
ok found '867511792.5951781', expected '867511792.5951782', error '0.0000000'
Test #53:
score: 0
Accepted
time: 511ms
memory: 59332kb
input:
200000 50 -2918 -7361 1022 7947 1922 8322 -2687 -1169 -7069 1584 -6718 6589 -9733 -6907 2142 4411 -343 -8490 6924 -7522 2602 -8627 10000 3353 -897 4353 -467 -9297 4708 -5094 -9632 -6922 7043 -2548 -6974 6170 5568 8821 -9952 -9320 -6399 3350 -1914 1032 -8378 -7784 8614 4495 -6310 -7880 -2388 4103 391...
output:
978924220.152041673660
result:
ok found '978924220.1520417', expected '978924220.1520417', error '0.0000000'
Test #54:
score: 0
Accepted
time: 508ms
memory: 61112kb
input:
200000 50 2851 -3667 9306 -9534 -3113 517 -9092 -8828 -9007 -8352 6918 -3354 -5062 8780 6287 -633 -8993 -21 -5049 8138 4110 6142 6009 8534 -4468 5223 -4345 984 -5974 7676 8313 8504 5200 -1257 4920 6613 409 -7591 -9635 -1093 -4327 1338 -533 1628 4520 -3597 -5263 -9301 7683 9652 8503 -1786 4506 8027 -...
output:
774758696.455128669739
result:
ok found '774758696.4551287', expected '774758696.4551287', error '0.0000000'
Extra Test:
score: 0
Extra Test Passed