QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#82217#5355. 多边形上天Recalling_Clouds10 23ms4160kbC++144.2kb2023-02-27 11:16:332023-02-27 11:16:34

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-27 11:16:34]
  • 评测
  • 测评结果:10
  • 用时:23ms
  • 内存:4160kb
  • [2023-02-27 11:16:33]
  • 提交

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;
}

详细

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%