QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#467673 | #6118. Eartheart | skip2004 | WA | 62ms | 23804kb | C++20 | 3.1kb | 2024-07-08 17:06:43 | 2024-07-08 17:06:43 |
Judging History
answer
// test
// https://qoj.ac/submission/467496
#include <bits/stdc++.h>
using namespace std;
typedef long double LD;
const LD eps = 1e-8;
const LD INF = 1e18;
int sgn (LD x) { return x > eps ? 1 : (x < -eps ? -1 : 0); }
#define cp const point &
struct point {
LD x, y;
point operator + (cp a) const { return {x + a.x, y + a.y}; }
point operator - (cp a) const { return {x - a.x, y - a.y}; }
point operator * (LD a) const { return {x * a, y * a}; }
point operator / (LD a) const { return {x / a, y / a}; }
point unit() const {
LD s = hypot (x, y);
return {x / s, y / s};
}
point rot90() const { return {-y, x}; }
};
LD det (cp a, cp b) { return a.x * b.y - b.x * a.y; }
LD dot (cp a, cp b) { return a.x * b.x + a.y * b.y; }
#define cl const line &
struct line {
point s, t;
};
point line_inter (cl a, cl b) {
LD s1 = det (a.t - a.s, b.s - a.s);
LD s2 = det (a.t - a.s, b.t - a.s);
return (b.s * s2 - b.t * s1) / (s2 - s1);
}
bool two_side (cp a, cp b, cl c) {
return (sgn (det (a - c.s, c.t - c.s)) <= 0) + (sgn (det (b - c.s, c.t - c.s)) <= 0) == 1;
}
void work() {
LD R;
int n;
cin >> n >> R;
R -= 3e-7;
vector <point> a;
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
a.push_back({x, y});
}
{
LD area = 0;
for (int i = 0; i < n; i++) area += det (a[i], a[(i + 1) % n]);
if (area < 0) {
reverse(a.begin(), a.end());
}
}
vector < pair <LD, int> > e;
for (int i = 0; i < n; i++) {
point u = a[i % n];
point v = a[(i + 1) % n];
if (sgn(u.y) <= 0 && sgn(v.y) > 0) {
e.push_back({line_inter ({u, v}, {{0, 0}, {1, 0}}).x, -1});
} else if (sgn (u.y) > 0 && sgn (v.y) <= 0) {
e.push_back({line_inter ({u, v}, {{0, 0}, {1, 0}}).x, 1});
}
}
for (int i = 0; i < n; i++) {
point u = a[i % n];
if (abs(u.y) < R) {
LD dx = sqrt(R * R - u.y * u.y);
e.push_back({u.x - dx, 2});
e.push_back({u.x + dx, -2});
}
point v = a[(i + 1) % n];
if (max(u.y, v.y) <= -R) continue;
if (min(u.y, v.y) >= R) continue;
point norm = (v - u).rot90().unit();
point w = v + norm * R;
point x = u + norm * R;
if (!sgn(w.y) && !sgn(x.y)) continue;
vector <line> lines = {
{u, v},
{v, w},
{w, x},
{x, u}
};
vector <LD> inter;
for (auto l : lines) {
if (two_side (l.s, l.t, {{0, 0}, {1, 0}})) {
inter.push_back(line_inter (l, {{0, 0}, {1, 0}}).x);
}
}
sort(inter.begin(), inter.end());
if (inter.size() && inter.back() - inter.front() > eps) {
e.push_back({inter.front(), 2});
e.push_back({inter.back(), -2});
}
}
sort(e.begin(), e.end());
LD last = -INF, ans = 0;
int cnt = 0, ban = 0;
for (auto [x, d] : e) {
//cerr << "last = " << last << " x = " << x << " " << cnt << " " << ban << endl;
if (cnt == 1 && !ban) ans += x - last;
if (abs(d) == 1) {
cnt += d;
} else {
ban += d;
}
assert (0 <= cnt && cnt <= 1);
last = x;
}
assert (cnt == 0);
cout << fixed << setprecision(9) << ans << '\n';
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int T = 1;
// cin >> T;
for (int ca = 1; ca <= T; ca ++) {
work();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 4056kb
input:
4 5 -5 -5 5 -5 5 5 -5 5
output:
0.000000600
result:
ok found '0.00000', expected '0.00000', error '0.00000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
4 5 -10 -10 10 -10 10 10 -10 10
output:
10.000000600
result:
ok found '10.00000', expected '10.00000', error '0.00000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3980kb
input:
9 10 -100 -80 -90 130 -30 150 0 160 100 130 120 90 110 -60 80 -100 0 -120
output:
190.156947758
result:
ok found '190.15695', expected '190.15695', error '0.00000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 4056kb
input:
457 414687 -996315 -725321 -986403 -603614 -984900 -99226 -943685 -319681 -985352 -704158 -984699 -905259 -969935 -927143 -465900 -963727 -310171 -992145 -453426 -949729 -643489 -909695 -709791 -884030 -787622 -849046 -526296 -903166 -408863 -906869 -263787 -933392 -473870 -789072 -593393 -759966 -6...
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #5:
score: 0
Accepted
time: 2ms
memory: 4288kb
input:
3157 635592 -998983 -17775 -993005 314040 -992532 -397616 -989247 708857 -985292 589314 -982046 726451 -979965 687632 -985621 240199 -978188 782690 -976339 41585 -981782 -274061 -974948 -410150 -980813 -585511 -980789 -865528 -981492 -862416 -984939 -322700 -984251 -496171 -985237 -472502 -991879 -4...
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4076kb
input:
1105 296370 -995471 952274 -991091 -838912 -968716 -981056 -955777 -928445 -879545 -975529 -834750 -968694 -825703 -878252 -787229 -998682 -764718 -954650 -732902 -919340 -610938 -966507 -267412 -971184 -68946 -980880 -178705 -973066 -291779 -953553 -347594 -912646 -338352 -904672 -270551 -821414 -1...
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4004kb
input:
179 22982 -998218 -375932 -924871 -833274 -965464 -861372 -304042 -941903 46407 -942280 576051 -973956 150160 -901679 604511 -911920 778636 -915852 -865584 -871767 -768265 -792995 -593904 -801716 -31277 -868485 479247 -885297 797358 -910090 449130 -870385 370979 -829124 -438450 -784467 -739280 -6550...
output:
497512.615655546
result:
ok found '497512.61566', expected '497512.61565', error '0.00000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 4216kb
input:
3292 364845 -999918 23115 -999238 -495220 -996555 524055 -993572 419978 -990246 -441487 -988731 493394 -987187 271949 -990286 -487104 -991159 -687002 -990332 -768047 -993275 -524304 -995312 -47770 -996316 -77665 -996912 -928704 -990291 -798112 -987083 -940798 -989169 -241346 -987846 -234987 -972976 ...
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #9:
score: 0
Accepted
time: 1ms
memory: 4048kb
input:
431 245611 -999674 -738083 -962850 -478189 -941103 -683461 -950693 -723371 -805609 -881791 -714279 -987279 -734606 -917431 -729365 -889819 -579494 -900362 -550372 -834907 -904231 -720665 -869101 -717255 -824019 -711973 -565569 -769652 -515548 -724811 -361500 -998030 -366800 -967623 -309405 -965964 -...
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 4108kb
input:
4628 771925 -999694 -176559 -999057 559136 -997722 740255 -998118 -532115 -997228 75078 -995395 -886460 -997053 153364 -995648 107732 -995663 368365 -988307 591328 -987914 444405 -990856 376975 -989333 106701 -984376 333516 -986560 116181 -990328 -66424 -981382 191264 -987644 -210220 -991226 -68250 ...
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #11:
score: 0
Accepted
time: 2ms
memory: 4212kb
input:
2937 717845 -998210 -682431 -996872 -887362 -984299 -865479 -960730 -958800 -959288 -998581 -915390 -941386 -915084 -941225 -870233 -992911 -759945 -996265 -463081 -993143 185428 -998477 309666 -999404 255022 -976930 229775 -959030 230936 -961109 234734 -972436 218732 -965431 260601 -995989 103112 -...
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #12:
score: 0
Accepted
time: 3ms
memory: 4148kb
input:
4511 974292 -999476 -606738 -999096 -723712 -992306 -944394 -991809 -987714 -988923 -835882 -990546 -197898 -989906 -224486 -988631 -715774 -985857 -696734 -984655 -673361 -983650 -593114 -984945 -565742 -986117 -314889 -983507 12004 -977152 -542680 -962273 -871586 -966937 -809794 -970586 -733453 -9...
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #13:
score: 0
Accepted
time: 1ms
memory: 4072kb
input:
1482 953437 -999701 -531118 -993174 -257827 -980094 -924148 -960541 -858744 -953510 -870425 -947870 -987956 -936077 -885214 -960348 -802355 -976424 -644804 -985648 -558705 -987112 -373731 -973395 -283308 -969368 -107184 -959895 -513223 -949966 -404476 -942421 -481016 -956164 -614383 -947493 -714466 ...
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #14:
score: 0
Accepted
time: 3ms
memory: 4680kb
input:
10001 851814 -999848 293276 -999261 -639166 -998728 -369611 -998983 -17775 -993520 -962370 -992983 -876893 -991811 -990246 -997047 -253251 -995527 -431256 -992585 -645211 -991813 -912868 -991091 -838912 -992756 -569264 -987687 -914262 -996368 -205687 -992164 -433526 -992532 -397616 -991879 -431244 -...
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #15:
score: 0
Accepted
time: 4ms
memory: 4560kb
input:
10001 336169 -999896 577082 -999822 184210 -998594 -35591 -997796 258516 -996867 34117 -996756 -391496 -997881 -727378 -998210 -682431 -998056 -958016 -990958 -970394 -986200 -957419 -974805 -973552 -959288 -998581 -960730 -958800 -956901 -936187 -949352 -941331 -944301 -942604 -951341 -963718 -9528...
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #16:
score: 0
Accepted
time: 6ms
memory: 4708kb
input:
10001 788227 -999874 674874 -999099 699732 -999701 -171220 -999812 -224313 -999557 -160461 -998302 -245251 -998701 -635019 -998526 -736484 -998412 -818031 -998073 -96296 -997156 138491 -996595 -926080 -988909 -813093 -985644 -796265 -984394 -844416 -985689 -855227 -981891 -861305 -981316 -891524 -98...
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #17:
score: 0
Accepted
time: 3ms
memory: 4084kb
input:
10001 198360 -999842 932608 -999523 380111 -998834 139995 -998652 -117584 -998755 850942 -998037 845586 -997580 582854 -998349 -148853 -998515 -628231 -998201 -639030 -998116 -840988 -998114 -531248 -998320 -223776 -997232 569927 -997235 168891 -995406 569364 -994666 562210 -994000 34156 -995345 -25...
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #18:
score: 0
Accepted
time: 0ms
memory: 4336kb
input:
10001 327410 -999928 9352 -999585 -676208 -999113 -416060 -998934 -694011 -999013 -484553 -999191 11324 -999485 328101 -999204 546226 -998663 -864092 -999029 823882 -998181 -719693 -997646 -820651 -997029 -525350 -997576 58842 -998212 -291824 -998221 -526066 -998281 -157179 -998232 602133 -996352 -8...
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
19 87 -89 23 -31 -55 72 -30 92 9 29 -32 44 33 27 17 23 20 24 1 -46 -7 41 51 80 72 -61 5 -77 22 39 94 -4 71 -22 79 -46 97 -87 61
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
13 87 -61 7 -9 -82 -5 -62 -1 -16 27 -39 22 -53 28 -81 87 10 59 -20 68 -3 9 -5 32 87 -47 -6
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
13 24 -82 74 -64 -67 -45 -13 -26 2 100 -90 71 -54 74 -21 16 -14 98 -1 92 35 84 66 97 98 14 40
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3988kb
input:
18 23 -99 -55 -20 -81 -64 -64 69 -40 99 -97 57 -15 -11 -52 0 -22 80 11 62 100 23 96 63 73 18 14 13 77 -34 38 -24 2 -94 54 -83 -21
output:
2.956610391
result:
ok found '2.95661', expected '2.95661', error '0.00000'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
16 50 -76 37 -72 -77 4 -52 19 -75 37 -44 42 -33 45 -27 64 -27 70 -65 71 -34 68 -23 78 79 8 7 -7 95 -6 39 -72 56
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3976kb
input:
14 54 -93 -75 -29 -89 -76 -46 -38 -73 -47 -13 -13 -2 17 -65 61 -99 29 -30 85 81 84 81 -5 -7 72 90 -64 -6
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
9 44 -82 -23 17 -86 31 -12 66 -29 88 3 19 50 -33 -27 -70 -15 -55 37
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
16 73 -79 -81 -22 -93 12 -38 55 -4 94 -63 92 -10 87 98 2 92 41 40 -11 97 15 50 32 2 5 -29 -6 -63 -39 11 -42 58
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
20 62 -98 -54 -97 -60 73 -81 70 -39 1 -2 -5 12 -21 23 -31 24 -64 -29 -62 -22 -87 -8 -37 69 56 14 68 10 69 10 94 -81 76 28 28 58 -24 79 -84 41
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
9 99 -90 53 -66 -92 8 -93 -56 -37 0 -45 95 -88 -8 -30 41 49 -69 1
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #29:
score: 0
Accepted
time: 8ms
memory: 9348kb
input:
23758 42 999891 36 998928 178 999811 36 998891 178 999794 36 998852 178 999669 36 998717 178 999551 36 998128 178 999516 36 997501 178 999350 36 997181 178 999275 36 997001 178 998599 36 996786 178 998502 36 996660 178 998380 36 995557 178 998196 36 995222 178 997848 36 994381 178 997842 36 993623 1...
output:
181485.756136754
result:
ok found '181485.75614', expected '181485.74982', error '0.00000'
Test #30:
score: 0
Accepted
time: 62ms
memory: 23804kb
input:
89098 100 999972 87 999857 278 999943 87 999701 278 999659 87 999618 278 999651 87 999589 278 999621 87 999450 278 999579 87 999356 278 999553 87 999110 278 999516 87 999049 278 999443 87 998921 278 999386 87 998760 278 999353 87 998661 278 999333 87 998653 278 999307 87 998557 278 999152 87 998537 ...
output:
42.837794014
result:
ok found '42.83779', expected '42.83779', error '0.00000'
Test #31:
score: 0
Accepted
time: 11ms
memory: 5980kb
input:
17198 9 999818 3 999579 401 998839 3 999557 401 998313 3 999189 401 997890 3 998142 401 997541 3 998104 401 997100 3 998052 401 996425 3 998028 401 996340 3 997767 401 996000 3 997489 401 995998 3 996716 401 995447 3 996079 401 995059 3 995539 401 993759 3 994367 401 993753 3 993994 401 993667 3 992...
output:
19947.934505775
result:
ok found '19947.93451', expected '19947.93108', error '0.00000'
Test #32:
score: 0
Accepted
time: 9ms
memory: 5780kb
input:
12538 71 999508 -38 999900 224 999243 -38 997800 224 998518 -38 996913 224 996174 -38 996435 224 996122 -38 995267 224 995886 -38 993656 224 995158 -38 993254 224 993472 -38 991121 224 992934 -38 990973 224 992555 -38 990564 224 992374 -38 989040 224 991361 -38 988792 224 990504 -38 985959 224 98962...
output:
15527.864561140
result:
ok found '15527.86456', expected '15527.86407', error '0.00000'
Test #33:
score: 0
Accepted
time: 34ms
memory: 17292kb
input:
65730 79 999935 18 999936 311 999932 18 999770 311 999898 18 999749 311 999772 18 999643 311 999668 18 999362 311 999490 18 999332 311 998865 18 999310 311 998792 18 998986 311 998676 18 998971 311 998569 18 998863 311 998384 18 998748 311 998198 18 998650 311 997974 18 998631 311 997502 18 998581 3...
output:
741.210380125
result:
ok found '741.21038', expected '741.21037', error '0.00000'
Test #34:
score: 0
Accepted
time: 15ms
memory: 13276kb
input:
52762 24 999966 -12 999655 270 999878 -12 999605 270 999663 -12 999574 270 999643 -12 999485 270 999503 -12 999466 270 999442 -12 999434 270 999266 -12 999366 270 999237 -12 999295 270 999170 -12 999187 270 999110 -12 999165 270 998894 -12 999133 270 998819 -12 998892 270 998544 -12 998867 270 99844...
output:
51298.208612152
result:
ok found '51298.20861', expected '51298.20692', error '0.00000'
Test #35:
score: 0
Accepted
time: 12ms
memory: 8376kb
input:
22030 10 999623 -4 999638 312 999583 -4 999535 312 999533 -4 998106 312 998365 -4 997779 312 997727 -4 997682 312 997552 -4 997449 312 997546 -4 997246 312 996821 -4 994236 312 996487 -4 993684 312 996172 -4 992726 312 995518 -4 992509 312 995195 -4 992346 312 995160 -4 991850 312 994853 -4 991802 3...
output:
761340.793686323
result:
ok found '761340.79369', expected '761340.77233', error '0.00000'
Test #36:
score: 0
Accepted
time: 41ms
memory: 15312kb
input:
87406 33 999996 33 999948 110 999992 33 999782 110 999920 33 999667 110 999919 33 999343 110 999668 33 999327 110 999613 33 999312 110 999607 33 999288 110 999375 33 999229 110 999213 33 999091 110 999033 33 999076 110 998809 33 999054 110 998753 33 999049 110 998698 33 999014 110 998558 33 998846 1...
output:
28667.821538381
result:
ok found '28667.82154', expected '28667.82110', error '0.00000'
Test #37:
score: 0
Accepted
time: 13ms
memory: 6240kb
input:
27382 91 999756 88 999773 105 998972 88 999759 105 998867 88 999730 105 998638 88 999367 105 998591 88 999329 105 998512 88 999318 105 998398 88 998870 105 998334 88 998818 105 997611 88 998434 105 997005 88 998338 105 996684 88 998073 105 996666 88 997242 105 996538 88 997154 105 996383 88 996911 1...
output:
2698.561654009
result:
ok found '2698.56165', expected '2698.56137', error '0.00000'
Test #38:
score: 0
Accepted
time: 48ms
memory: 14260kb
input:
78350 61 999971 21 999982 211 999858 21 999969 211 999751 21 999876 211 999742 21 999632 211 999648 21 999606 211 999613 21 999600 211 999578 21 999596 211 999462 21 999577 211 999384 21 999405 211 999335 21 999356 211 998897 21 999258 211 998879 21 999209 211 998651 21 999152 211 998395 21 999151 2...
output:
2180.247741699
result:
ok found '2180.24774', expected '2180.24768', error '0.00000'
Test #39:
score: 0
Accepted
time: 0ms
memory: 5380kb
input:
19372 42 1000000 779761 998891 779761 998891 13 998852 13 998852 779761 998717 779761 998717 -14 998128 -14 998128 779761 997501 779761 997501 -2 997181 -2 997181 779761 997001 779761 997001 -2 996786 -2 996786 779761 996660 779761 996660 39 995557 39 995557 779761 995222 779761 995222 -10 993623 -1...
output:
398726.544879201
result:
ok found '398726.54488', expected '398726.54294', error '0.00000'
Test #40:
score: -100
Wrong Answer
time: 22ms
memory: 14356kb
input:
78564 8 1000000 829540 999637 829540 999637 7 999618 7 999618 829540 999589 829540 999589 8 999426 8 999426 829540 999049 829540 999049 8 999004 8 999004 829540 998760 829540 998760 8 998661 8 998661 829540 998653 829540 998653 7 998557 7 998557 829540 998480 829540 998480 7 998319 7 998319 829540 9...
output:
737476.111279183
result:
wrong answer 1st numbers differ - expected: '697371.36384', found: '737476.11128', error = '0.05751'