QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#82217 | #5355. 多边形上天 | Recalling_Clouds | 10 | 23ms | 4160kb | C++14 | 4.2kb | 2023-02-27 11:16:33 | 2023-02-27 11:16:34 |
Judging History
answer
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(...) fprintf (stderr, __VA_ARGS__)
#define x first
#define y second
#define lep(i, l, r) for (int i = (l), i##_end = (r); i <= i##_end; ++ i)
#define rep(i, r, l) for (int i = (r), i##_end = (l); i >= i##_end; -- i)
char _c; bool _f; template <class T> inline void IN (T & x) {
_f = 0, x = 0; while (_c = getchar (), ! isdigit (_c)) if (_c == '-') _f = 1;
while (isdigit (_c)) x = x * 10 + _c - '0', _c = getchar (); if (_f == 1) x = -x;
}
template <class T> inline void chkmin (T & x, T y) { if (x < y) x = y; }
template <class T> inline void chkmax (T & x, T y) { if (x < y) x = y; }
const int N = 2e3 + 5;
const double eps = 1e-6;
const double pi = acos ( -1 );
const double g = 9.8;
const double inf = 1e18;
inline bool equal (double a, double b) { return fabs (a - b) < eps; }
double v, w, r, theta;
inline double f1 (double t) { return cos (theta - t * w) * w * r + g * t; }
inline double f2 (double t) { return sin (theta - t * w) * w * r + v; }
inline double calc1 (double L) { return (sin (theta) - sin (theta - L * w)) * r + L * L / 2 * g; }
inline double calc2 (double L) { return (cos (theta - L * w) - cos (theta)) * r + L * v; }
int n;
pair <double, double> c;
inline double findtp (double L, double R) {
for (int t = 50; t; -- t) {
double len = (R - L) / 3, m1 = L + len, m2 = R - len;
(f1 (m1) < f1 (m2)) ? L = m1 : R = m2;
}
return L;
}
inline double doit (int a, int b, double & ret_a) {
if (! b) return ret_a = a, 0;
r = sqrt ((c.x - a) * (c.x - a) + (c.y - b) * (c.y - b));
theta = atan2 (b - c.y, a - c.x);
double st = theta / w, T = pi / w;
double tp = findtp (st - T / 2, st + T / 2);
double shift = (st + T / 2 - tp) * 2;
swap (tp, st);
if (st > 0) st -= floor (st / (2 * T)) * 2 * T;
if (st < 0) st += ceil ( ( - st) / (2 * T)) * 2 * T;
if (shift < eps) {
double L = 0, R = 2e5;
for (int t = 50; t; -- t) {
double mid = (L + R) / 2;
calc1 (mid) >= b ? R = mid : L = mid;
}
return ret_a = a + calc2 (L), L;
}
auto findrt = [&] (double L) -> double {
double R = L + shift;
if (f1 (R) >= 0) return inf;
for (int t = 30; t; -- t) {
double mid = (L + R) / 2;
f1 (mid) >= 0 ? L = mid : R = mid;
}
return L;
};
double lt = findrt (st - 2 * T), ret = 0, tot;
if (equal (lt, inf)) ret = 0;
else {
int L = 0, R = 2e5; // st + mid * 2 * T
if (lt >= 0) st -= 2 * T;
while (L <= R) {
int mid = (L + R) >> 1;
double lp = findrt (st + 2 * mid * T);
! equal (lp, inf) ? tot = mid, ret = lp, L = mid + 1 : R = mid - 1;
}
}
if (calc1 (ret) < b) {
double L = ret, R = 1e6;
for (int t = 50; t; -- t) {
double mid = (L + R) / 2;
calc1 (mid) >= b ? R = mid : L = mid;
}
ret = L;
} else {
int L = 0, R = tot, pt = -1;
double lm;
while (L <= R) {
int mid = (L + R) >> 1;
double lp = findrt (st + 2 * mid * T);
assert (! equal (lp, inf));
calc1 (lp) >= b ? lm = lp, pt = mid, R = mid - 1 : L = mid + 1;
}
cout << pt << endl ;
assert ( ~ pt);
double A = st + 2 * (pt - 1) * T + shift, B = lm;
for (int t = 50; t; -- t) {
double mid = (A + B) / 2;
calc1 (mid) >= b ? B = mid : A = mid;
}
ret = A;
}
return ret_a = a + calc2 (ret), ret;
}
pair <int, int> p[N];
signed main () {
// freopen ( "nothing.in", "r", stdin ) ;
// freopen ( "nothing.out", "w", stdout ) ;
IN (n), IN (v), IN (w);
lep (i, 1, n) IN (p[i].x), IN (p[i].y);
lep (i, 1, n) c.x += p[i].x, c.y += p[i].y;
c.x /= n, c.y /= n;
double ans_t = inf, ans_a = 0;
lep (i, 1, n) {
double now_a, now_t = doit (p[i].x, p[i].y, now_a);
if (ans_t > now_t) swap (now_t, ans_t), swap (ans_a, now_a);
}
printf ("%.10lf\n", ans_a);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1ms
memory: 4004kb
input:
8 53 0 11 935 11 945 1 935 61 915 121 935 111 945 111 935 61 925
output:
785.2497877469
result:
ok found '785.24979', expected '785.24979', error '0.00000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4084kb
input:
4 931 0 1 867 51 847 101 867 51 887
output:
12291.3361874017
result:
ok found '12291.33619', expected '12291.33619', error '0.00000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
8 721 0 1 313 21 303 41 313 41 318 61 313 61 308 81 313 41 333
output:
5690.6798847167
result:
ok found '5690.67988', expected '5690.67988', error '0.00000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3868kb
input:
10 303 0 1 545 21 535 41 545 46 545 41 550 61 545 66 545 61 540 81 545 41 565
output:
3187.0770484851
result:
ok found '3187.07705', expected '3187.07705', error '0.00000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 4000kb
input:
26 244 0 4 925 9 928 10 927 24 936 24 937 29 940 31 939 44 948 44 949 49 952 54 951 64 955 63 961 59 958 54 955 52 957 39 947 39 946 34 943 30 945 19 935 19 934 14 931 12 932 1 927 4 924
output:
3354.6400241059
result:
ok found '3354.64002', expected '3354.64002', error '0.00000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
20 854 0 7 404 3 396 5 395 8 401 18 396 12 384 4 388 5 390 11 387 15 395 9 398 7 394 9 393 10 395 12 394 10 390 4 393 1 387 13 381 21 397
output:
7543.4740880551
result:
ok found '7543.47409', expected '7543.47409', error '0.00000'
Test #7:
score: 0
Accepted
time: 2ms
memory: 4124kb
input:
16 701 0 6 400 16 395 26 400 36 415 46 400 51 410 46 420 31 430 46 440 36 445 26 440 16 425 6 440 1 430 6 420 21 410
output:
6309.8809768243
result:
ok found '6309.88098', expected '6309.88097', error '0.00000'
Test #8:
score: 0
Accepted
time: 2ms
memory: 4004kb
input:
7 906 0 1 531 51 581 81 551 111 581 71 621 41 591 1 631
output:
9432.4272296323
result:
ok found '9432.42723', expected '9432.42723', error '0.00000'
Test #9:
score: 0
Accepted
time: 2ms
memory: 4148kb
input:
4 462 0 1 957 101 857 201 957 101 1057
output:
6210.9034360286
result:
ok found '6210.90344', expected '6210.90343', error '0.00000'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3964kb
input:
3 25 0 2018 4322 1 288 4035 2305
output:
192.6629694954
result:
ok found '192.66297', expected '192.66297', error '0.00000'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3972kb
input:
7 702 0 1 373 41 353 41 373 71 403 51 423 31 403 1 403
output:
5999.3556831644
result:
ok found '5999.35568', expected '5999.35568', error '0.00000'
Test #12:
score: 0
Accepted
time: 22ms
memory: 3960kb
input:
1998 429 0 3767 3138 3780 3092 3746 3125 3710 3223 3620 3249 3613 3342 3675 3373 3740 3341 3666 3457 3593 3437 3550 3491 3602 3524 3643 3502 3568 3561 3489 3464 3487 3418 3506 3408 3612 3358 3593 3361 3537 3387 3612 3272 3516 3353 3411 3408 3450 3346 3505 3252 3406 3373 3340 3427 3352 3470 3290 3367...
output:
5326.8800009631
result:
ok found '5326.88000', expected '5326.88000', error '0.00000'
Test #13:
score: 0
Accepted
time: 20ms
memory: 4012kb
input:
1999 314 0 1248 1040 1248 1028 1222 979 1239 997 1234 999 1310 984 1263 1000 1312 1007 1400 993 1351 1066 1342 1048 1358 1116 1431 998 1430 1059 1467 1025 1432 885 1413 905 1405 932 1361 914 1379 943 1398 990 1318 943 1296 963 1313 917 1287 920 1298 937 1279 934 1280 943 1281 968 1277 966 1255 984 1...
output:
2680.1561402367
result:
ok found '2680.15614', expected '2680.15614', error '0.00000'
Test #14:
score: 0
Accepted
time: 23ms
memory: 4140kb
input:
2000 585 0 7253 8738 7199 11592 7219 11938 7222 14798 7217 18958 7058 20006 7449 19631 7199 19795 7369 18858 7432 12009 7365 11908 7323 13461 7310 18417 7333 2500 7329 4885 7301 2464 7300 18396 7293 13514 7266 19388 7291 4352 7295 1322 6817 113 10834 149 11482 272 11172 598 11315 1326 11374 2269 113...
output:
21715.6928372179
result:
ok found '21715.69284', expected '21715.69284', error '0.00000'
Test #15:
score: 0
Accepted
time: 22ms
memory: 3920kb
input:
2000 783 0 13294 14681 14130 14748 14670 15645 14783 15871 14423 16189 13914 16310 14131 16461 14360 16660 14699 16275 16259 16583 15836 15846 16286 15799 16707 16065 16175 16807 16352 17189 16183 16957 15735 16598 15065 16574 15820 17128 14875 17847 15088 17368 14829 16467 14787 16801 14788 17099 1...
output:
15094.2334394825
result:
ok found '15094.23344', expected '15094.23344', error '0.00000'
Test #16:
score: 0
Accepted
time: 9ms
memory: 3840kb
input:
1004 252 0 7001 107 7000 107 6999 107 6998 107 6997 107 6996 107 6995 107 6994 107 6993 107 6992 107 6991 107 6990 107 6989 107 6988 107 6987 107 6986 107 6985 107 6984 107 6983 107 6982 107 6981 107 6980 107 6979 107 6978 107 6977 107 6976 107 6975 107 6974 107 6973 107 6972 107 6971 107 6970 107 6...
output:
1161.9651155631
result:
ok found '1161.96512', expected '1161.96512', error '0.00000'
Test #17:
score: 0
Accepted
time: 7ms
memory: 4008kb
input:
500 182 0 6427 102 6449 123 6472 145 6496 168 6521 192 6547 217 6574 243 6661 327 6692 357 6693 358 6723 389 6752 419 6780 448 6833 503 6882 554 6905 578 6948 623 6968 644 6987 664 7005 683 7022 701 7038 718 7053 734 7082 765 7123 809 7161 850 7173 863 7196 888 7207 900 7228 923 7257 955 7285 986 72...
output:
7257.3734098689
result:
ok found '7257.37341', expected '7257.37341', error '0.00000'
Test #18:
score: 0
Accepted
time: 21ms
memory: 4008kb
input:
2000 322 0 9908 20007 9903 20002 9901 20000 9900 19999 9878 19977 9821 19920 9809 19908 9805 19904 9804 19903 9763 19862 9748 19847 9733 19832 9719 19818 9711 19810 9707 19806 9667 19766 9573 19672 9535 19634 9527 19626 9524 19623 9515 19614 9497 19596 9467 19566 9465 19564 9428 19527 9396 19495 938...
output:
11455.6477235164
result:
ok found '11455.64772', expected '11455.64772', error '0.00000'
Test #19:
score: 0
Accepted
time: 2ms
memory: 3968kb
input:
4 302 0 1 10107 10001 107 20001 10107 10001 20107
output:
11412.2397210937
result:
ok found '11412.23972', expected '11412.23972', error '0.00000'
Test #20:
score: 0
Accepted
time: 9ms
memory: 4156kb
input:
1000 306 0 17907 9955 19014 10012 18876 10068 15563 10063 15295 10092 16681 10170 19168 10307 16945 10268 14828 10207 14832 10238 17217 10420 18725 10571 19786 10708 19252 10727 17435 10626 15184 10462 16712 10650 18372 10872 15959 10652 16618 10771 19580 11188 18841 11152 18435 11154 15258 10747 18...
output:
12829.2617330775
result:
ok found '12829.26173', expected '12829.26173', error '0.00000'
Test #21:
score: 0
Accepted
time: 4ms
memory: 3840kb
input:
500 913 0 19773 9874 16724 9959 17432 10063 17292 10152 15090 10134 17165 10330 16636 10381 17560 10548 16810 10569 15430 10500 14917 10506 19243 11172 14855 10625 19350 11429 16373 11022 19549 11712 15224 10956 19318 11914 18153 11770 17965 11834 18627 12111 16310 11602 14949 11303 14767 11317 1728...
output:
12904.3687551092
result:
ok found '12904.36876', expected '12904.36876', error '0.00000'
Test #22:
score: 0
Accepted
time: 1ms
memory: 3964kb
input:
100 731 0 15416 9434 14837 9754 18960 10598 16064 10640 15278 10855 16921 11766 18528 12913 18521 13565 16301 13040 16158 13506 17275 14908 17090 15513 14842 14224 15483 15549 13895 14455 14359 15790 13566 15461 12530 14507 13728 17906 11840 14735 11755 15632 11503 16296 11516 18741 10599 16227 1013...
output:
11377.9478017202
result:
ok found '11377.94780', expected '11377.94780', error '0.00000'
Test #23:
score: 0
Accepted
time: 12ms
memory: 4160kb
input:
1000 870 0 20001 10105 20000 10167 20000 10230 19999 10293 19997 10356 19996 10419 19993 10481 19991 10544 19988 10607 19985 10670 19981 10732 19977 10795 19972 10858 19967 10920 19962 10983 19956 11046 19950 11108 19944 11171 19937 11233 19929 11295 19922 11358 19914 11420 19905 11482 19896 11545 1...
output:
14028.3174336747
result:
ok found '14028.31743', expected '14028.31744', error '0.00000'
Test #24:
score: 0
Accepted
time: 3ms
memory: 3908kb
input:
500 649 0 20001 10107 20000 10232 19997 10358 19993 10483 19988 10609 19981 10734 19972 10860 19962 10985 19950 11110 19937 11235 19922 11360 19905 11484 19887 11609 19867 11733 19846 11857 19823 11980 19799 12104 19773 12227 19746 12349 19717 12471 19686 12593 19654 12715 19621 12836 19586 12957 19...
output:
13033.7635065888
result:
ok found '13033.76351', expected '13033.76351', error '0.00000'
Test #25:
score: 0
Accepted
time: 1ms
memory: 3904kb
input:
100 603 0 20001 10104 19981 10731 19922 11357 19823 11977 19686 12590 19511 13194 19298 13785 19049 14361 18764 14921 18444 15462 18091 15981 17706 16478 17290 16949 16846 17393 16375 17809 15878 18194 15359 18547 14818 18867 14258 19152 13682 19401 13091 19614 12487 19789 11874 19926 11254 20025 10...
output:
12779.0236693831
result:
ok found '12779.02367', expected '12779.02367', error '0.00000'
Test #26:
score: 0
Accepted
time: 2ms
memory: 4152kb
input:
28 541 0 91 143 161 108 324 135 419 226 372 474 368 313 322 393 307 203 285 524 282 304 234 174 232 315 220 400 217 493 214 133 185 180 183 433 169 550 156 363 137 195 107 299 101 247 95 396 86 320 63 501 44 248 1 426 17 183
output:
2700.8677448027
result:
ok found '2700.86774', expected '2700.86775', error '0.00000'
Test #27:
score: 0
Accepted
time: 2ms
memory: 4084kb
input:
10 558 0 111 271 58 221 57 202 8 117 102 124 66 134 71 143 158 106 135 120 94 154
output:
2753.3091117312
result:
ok found '2753.30911', expected '2753.30911', error '0.00000'
Test #28:
score: 0
Accepted
time: 2ms
memory: 3964kb
input:
5 742 0 21 308 11 408 11 208 1 308 11 108
output:
3494.5154651454
result:
ok found '3494.51547', expected '3494.51547', error '0.00000'
Test #29:
score: 0
Accepted
time: 2ms
memory: 4124kb
input:
5 91 0 101 119 301 109 201 119 401 119 301 129
output:
730.1969244896
result:
ok found '730.19692', expected '730.19692', error '0.00000'
Test #30:
score: 0
Accepted
time: 2ms
memory: 3952kb
input:
5 731 0 1 103 101 203 52 152 201 303 50 154
output:
3352.4901648113
result:
ok found '3352.49016', expected '3352.49016', error '0.00000'
Test #31:
score: 0
Accepted
time: 0ms
memory: 4152kb
input:
5 865 0 1 104 101 204 61 144 121 224 41 164
output:
3986.0588292145
result:
ok found '3986.05883', expected '3986.05883', error '0.00000'
Test #32:
score: 0
Accepted
time: 2ms
memory: 4124kb
input:
5 133 0 1 108 101 208 61 148 201 308 41 168
output:
625.4037154506
result:
ok found '625.40372', expected '625.40372', error '0.00000'
Test #33:
score: 0
Accepted
time: 2ms
memory: 3944kb
input:
8 600 0 1 104 21 134 1 164 1 154 1 144 1 134 1 124 1 114
output:
2765.2026561026
result:
ok found '2765.20266', expected '2765.20266', error '0.00000'
Test #34:
score: 0
Accepted
time: 2ms
memory: 3904kb
input:
4 359 0 1 208 56 163 101 108 101 208
output:
1786.4205552388
result:
ok found '1786.42056', expected '1786.42056', error '0.00000'
Test #35:
score: 0
Accepted
time: 2ms
memory: 4008kb
input:
4 298 0 1 114 11 104 101 194 91 204
output:
1383.8873191976
result:
ok found '1383.88732', expected '1383.88732', error '0.00000'
Test #36:
score: 0
Accepted
time: 2ms
memory: 4152kb
input:
4 422 0 1 107 101 106 102 206 2 207
output:
2063.7606543917
result:
ok found '2063.76065', expected '2063.76066', error '0.00000'
Test #37:
score: 0
Accepted
time: 2ms
memory: 3964kb
input:
4 732 0 101 105 201 205 101 305 1 205
output:
3489.5015648849
result:
ok found '3489.50156', expected '3489.50157', error '0.00000'
Test #38:
score: 0
Accepted
time: 1ms
memory: 3936kb
input:
3 893 0 1 108 20001 20107 20000 20108
output:
4193.4249465968
result:
ok found '4193.42495', expected '4193.42495', error '0.00000'
Test #39:
score: 0
Accepted
time: 2ms
memory: 3916kb
input:
3 262 0 10001 20106 10000 20106 10001 106
output:
11219.5859986982
result:
ok found '11219.58600', expected '11219.58600', error '0.00000'
Test #40:
score: 0
Accepted
time: 2ms
memory: 3904kb
input:
3 866 0 20001 204 1 204 20001 104
output:
23990.6658336414
result:
ok found '23990.66583', expected '23990.66583', error '0.00000'
Test #41:
score: 0
Accepted
time: 0ms
memory: 4020kb
input:
3 616 0 20001 104 1 104 20001 103
output:
22825.2379501009
result:
ok found '22825.23795', expected '22825.23795', error '0.00000'
Test #42:
score: 0
Accepted
time: 2ms
memory: 3968kb
input:
5 551 0 1 106 2 108 2 111 1 108 1 107
output:
2563.7514705446
result:
ok found '2563.75147', expected '2563.75147', error '0.00000'
Subtask #2:
score: 0
Wrong Answer
Test #43:
score: 0
Wrong Answer
time: 0ms
memory: 4000kb
input:
8 811 14 11 911 11 921 1 911 61 891 121 911 111 921 111 911 61 901
output:
29 29 29 30 30 30 30 10885.3995714496
result:
wrong answer 1st numbers differ - expected: '10885.39957', found: '29.00000', error = '0.99734'
Subtask #3:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%