QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#821113#9869. Horizon ScanningvwxyzAC ✓38ms7656kbC++234.0kb2024-12-19 13:20:542024-12-19 13:20:55

Judging History

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

  • [2024-12-19 13:20:55]
  • 评测
  • 测评结果:AC
  • 用时:38ms
  • 内存:7656kb
  • [2024-12-19 13:20:54]
  • 提交

answer

// competitive-verifier: PROBLEM
#ifdef ATCODER
#pragma GCC target("sse4.2,avx512f,avx512dq,avx512ifma,avx512cd,avx512bw,avx512vl,bmi2")
#endif
#pragma GCC optimize("Ofast,fast-math,unroll-all-loops")
#include <bits/stdc++.h>
#ifndef ATCODER
#pragma GCC target("sse4.2,avx2,bmi2")
#endif
template <class T, class U>
constexpr bool chmax(T &a, const U &b) {
    return a < (T)b ? a = (T)b, true : false;
}
template <class T, class U>
constexpr bool chmin(T &a, const U &b) {
    return (T)b < a ? a = (T)b, true : false;
}
constexpr std::int64_t INF = 1000000000000000003;
constexpr int Inf = 1000000003;
constexpr double EPS = 1e-7;
constexpr double PI = 3.14159265358979323846;
#define FOR(i, m, n) for (int i = (m); i < int(n); ++i)
#define FORR(i, m, n) for (int i = (m)-1; i >= int(n); --i)
#define FORL(i, m, n) for (int64_t i = (m); i < int64_t(n); ++i)
#define rep(i, n) FOR (i, 0, n)
#define repn(i, n) FOR (i, 1, n + 1)
#define repr(i, n) FORR (i, n, 0)
#define repnr(i, n) FORR (i, n + 1, 1)
#define all(s) (s).begin(), (s).end()
struct Sonic {
    Sonic() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        std::cout << std::fixed << std::setprecision(20);
    }
    constexpr void operator()() const {}
} sonic;
using namespace std;
using ll = std::int64_t;
using ld = long double;
template <class T, class U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
    return is >> p.first >> p.second;
}
template <class T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
    for (T &i : v) is >> i;
    return is;
}
template <class T, class U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &p) {
    return os << '(' << p.first << ',' << p.second << ')';
}
template <class T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
    for (auto it = v.begin(); it != v.end(); ++it) os << (it == v.begin() ? "" : " ") << *it;
    return os;
}
template <class Head, class... Tail>
void co(Head &&head, Tail &&...tail) {
    if constexpr (sizeof...(tail) == 0) std::cout << head << '\n';
    else std::cout << head << ' ', co(std::forward<Tail>(tail)...);
}
template <class Head, class... Tail>
void ce(Head &&head, Tail &&...tail) {
    if constexpr (sizeof...(tail) == 0) std::cerr << head << '\n';
    else std::cerr << head << ' ', ce(std::forward<Tail>(tail)...);
}
void Yes(bool is_correct = true) { std::cout << (is_correct ? "Yes\n" : "No\n"); }
void No(bool is_not_correct = true) { Yes(!is_not_correct); }
void YES(bool is_correct = true) { std::cout << (is_correct ? "YES\n" : "NO\n"); }
void NO(bool is_not_correct = true) { YES(!is_not_correct); }
void Takahashi(bool is_correct = true) { std::cout << (is_correct ? "Takahashi" : "Aoki") << '\n'; }
void Aoki(bool is_not_correct = true) { Takahashi(!is_not_correct); }
// 偏角ソート
// void arg_sort(vector<pair<ll, ll>> &v) {
//     auto sign = [&](const pair<ll, ll> &p) -> int {
//         if (p.first == 0 && p.second == 0)
//             return 0;
//         else if (p.second < 0 || (p.second <= 0 && p.first > 0))
//             return -1;
//         else
//             return 1;
//     };
//     auto cmp = [&](const pair<ll, ll> &p, const pair<ll, ll> &q) -> bool {
//         return (sign(p) != sign(q) ? sign(p) < sign(q)
//                                    : p.first * q.second - p.second * q.first > 0);
//     };
//     sort(v.begin(), v.end(), cmp);
// }
void solve() {
    int n, k;
    cin >> n >> k;
    vector<pair<ll, ll>> a(n);
    cin >> a;
    if (n == k) {
        co(2 * M_PI);
        return;
    }
    vector<double> b(n);
    rep (i, n) b[i] = atan2(a[i].second, a[i].first);
    sort(all(b));
    double ans = 0;
    rep (i, n) {
        int x = i;
        int y = (i + k) % n;
        if (x <= y) {
            chmax(ans, b[y] - b[x]);
        } else {
            chmax(ans, M_PI * 2 + b[y] - b[x]);
        }
    }
    co(ans);
}
int main(void) {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4248kb

input:

5
1 1
0 1
8 2
1 0
1 1
0 1
-1 1
-1 0
-1 -1
0 -1
1 -1
4 2
-1 1
0 1
0 2
1 1
4 2
-1000000000 0
-998244353 1
998244353 1
1000000000 0
3 1
0 1
0 2
0 -1

output:

6.28318530717958623200
1.57079632679489655800
5.49778714378213795300
3.14159265459155179201
3.14159265358979311600

result:

ok 5 numbers

Test #2:

score: 0
Accepted
time: 22ms
memory: 4308kb

input:

10000
16 1
-10 -6
-5 -6
-4 9
-2 5
-2 10
1 -7
1 -5
1 6
3 1
4 -9
6 -10
6 -3
6 1
8 -5
8 -4
9 -4
17 4
-9 2
-8 -4
-8 -3
-8 -1
-6 -2
-6 -1
-6 8
-5 -8
-5 10
-4 8
-2 -8
4 -9
4 0
5 -3
8 -5
9 -2
10 10
10 6
-7 2
-4 6
-2 -7
-2 -1
-1 7
1 -9
1 8
3 -4
7 -4
9 -2
14 3
-9 10
-8 -10
-8 -8
-6 -7
-6 -5
-1 -7
-1 -2
0 -1
...

output:

1.69299149748625143985
2.57486343606628675929
4.65275826725352015245
2.77263310738393631283
5.74276580690900217974
4.85769899102039204308
3.41989231259490455983
2.81279996208483851206
6.28318530717958623200
6.28318530717958623200
5.11728076666977305109
6.14678270277863880722
3.84208902353751957648
2...

result:

ok 10000 numbers

Test #3:

score: 0
Accepted
time: 22ms
memory: 4208kb

input:

10000
19 7
-10 -6
-10 5
-3 0
-2 -5
-1 1
-1 6
0 3
0 7
1 9
3 -3
3 3
3 8
4 -1
5 8
6 -3
7 -5
7 4
8 10
9 -5
15 15
-9 -1
-8 6
-7 9
-6 -3
-4 -9
-1 -3
-1 8
1 -8
1 -7
3 -2
3 1
6 -9
7 -10
7 0
10 -9
10 3
-7 -1
-6 -2
-6 10
-5 2
-4 2
-3 -7
-2 -9
1 -3
3 4
7 7
15 4
-8 -8
-8 8
-7 0
-7 10
-6 -7
-5 6
-1 -3
-1 0
1 -2
...

output:

3.92699081698724139500
6.28318530717958623200
3.36026159946373503828
2.67794504458898696697
3.77038894000522617489
1.76258446878160190963
3.84025247831125637887
5.49778714378213795300
2.03444393579570270703
1.81577498992176078474
4.34718753059651685788
6.14128825257542221294
5.17603658938549582302
5...

result:

ok 10000 numbers

Test #4:

score: 0
Accepted
time: 23ms
memory: 4236kb

input:

10000
18 12
-10 -4
-10 7
-8 -10
-7 -4
-6 5
-6 7
-5 0
-2 -7
-1 2
-1 10
0 2
1 1
3 -2
5 3
5 5
6 -3
8 -3
9 -2
10 1
-10 -9
-7 -7
-5 2
-4 -7
-3 1
3 1
3 3
5 -4
9 2
9 6
11 2
-8 1
-8 6
-7 -2
-6 0
-5 0
-1 -9
2 -8
3 5
6 0
10 -2
10 6
20 9
-10 -6
-10 6
-9 -8
-7 5
-6 -4
-4 -8
-2 -10
-2 -3
-2 4
-1 1
2 -5
3 -2
5 -6...

output:

4.90978454023457011601
1.97568811307997993509
1.98686083251871936639
3.92699081698724139500
3.69775888371024574752
6.28318530717958623200
6.14128825257542221294
6.19387131418636371905
5.80535425218747125342
6.25289154726081086721
5.72887781097803472363
3.09009184263856795383
1.89254688119153868797
5...

result:

ok 10000 numbers

Test #5:

score: 0
Accepted
time: 22ms
memory: 4208kb

input:

10000
19 7
-10 -1
-8 2
-7 -10
-6 6
-4 7
-3 -5
-3 1
-3 8
-2 4
-1 -7
0 -8
0 9
1 -10
2 1
2 3
3 5
6 -4
10 2
10 3
14 10
-8 2
-6 0
-5 -10
-5 10
-4 7
-3 -6
-2 -6
1 4
1 6
2 -1
3 -6
8 -4
9 -10
10 -1
12 8
-9 5
-7 2
-4 2
0 -2
0 5
1 6
3 2
4 9
5 5
7 -6
9 -9
9 2
19 12
-10 -10
-10 2
-9 -6
-8 2
-7 -5
-6 8
-4 1
-1 -...

output:

3.23931956094851214445
5.27570524187665768068
5.30039158393225751098
5.38712992260824208302
5.88839418747982534796
4.11731935667914861199
1.13838855122435878009
1.51529782154917991299
6.14765759319408555683
6.15883031263282454404
2.57486343606628675929
5.94016136675888262175
1.60851427926176082650
4...

result:

ok 10000 numbers

Test #6:

score: 0
Accepted
time: 22ms
memory: 4220kb

input:

10000
11 10
-10 -1
-9 4
-9 10
-7 -7
-5 4
-4 -1
-2 -10
0 -7
0 5
3 3
3 5
12 12
-9 6
-9 8
-3 -2
-2 2
0 -4
1 0
2 -3
3 5
5 -2
7 -1
10 3
10 9
14 12
-10 0
-9 -3
-9 1
-9 10
-8 -1
-8 7
-6 -1
-1 -6
-1 2
1 -1
3 -7
4 9
9 -3
10 1
10 4
-9 -3
-7 -1
-6 -10
-3 -2
-3 7
2 -2
2 3
5 2
6 9
9 6
10 2
-9 -9
-9 6
-8 3
-5 -9
...

output:

6.13787529654388297473
6.28318530717958623200
6.11803662976495932213
3.20034847630551588793
2.65375621493015056984
6.25378201897558039235
3.60524026259059926502
3.55981698316902228640
1.50914615615563763029
5.92754942287882613527
6.25879989800686775681
2.62244653934327009992
4.39383330329662236124
5...

result:

ok 10000 numbers

Test #7:

score: 0
Accepted
time: 23ms
memory: 4212kb

input:

10000
14 1
-100 13
-96 -31
-82 -92
-77 -98
-50 1
-14 -57
-14 -31
-11 64
-8 75
9 68
25 100
54 -36
59 13
93 31
19 19
-76 -39
-60 95
-51 18
-39 11
-21 -46
-6 -94
-5 83
-3 -34
-3 72
0 -55
3 79
14 17
23 -88
32 37
50 70
61 -5
62 -43
84 -100
97 -50
13 7
-99 -63
-68 -87
-24 62
-20 -18
-2 -66
7 -49
13 -21
15...

output:

1.27130939746127902268
6.28318530717958623200
5.22251472073649836148
6.00306570356891811002
3.92587213546467950209
5.54652899509206953610
3.21031492371172344491
3.03993004992372295447
4.22753178179442556939
3.03201966573687720086
2.19121523381818983367
3.03900809036774077754
4.33132715063550310930
6...

result:

ok 10000 numbers

Test #8:

score: 0
Accepted
time: 18ms
memory: 4204kb

input:

100
1413 755
-30 -30
-30 -28
-30 -27
-30 -26
-30 -21
-30 -12
-30 -10
-30 -8
-30 -5
-30 -1
-30 2
-30 4
-30 7
-30 9
-30 17
-30 19
-30 20
-30 23
-30 24
-30 30
-29 -29
-29 -23
-29 -15
-29 0
-29 4
-29 5
-29 9
-29 10
-29 11
-29 12
-29 14
-29 16
-29 17
-29 22
-29 27
-29 28
-28 -28
-28 -25
-28 -23
-28 -22
-...

output:

3.58911262874696301850
2.97975522235137013638
0.28379410920832759402
2.03502770689109313551
4.88798114233487002167
1.00406710927139020129
4.74570997626293689109
5.32559632925919856916
4.31027496473292703882
5.60338367941383008741
1.57980509208531350041
4.32964547053911452679
5.54722209679409150596
1...

result:

ok 100 numbers

Test #9:

score: 0
Accepted
time: 22ms
memory: 4528kb

input:

20
9045 8319
-1000 -986
-1000 -683
-1000 -430
-1000 -292
-1000 53
-1000 667
-999 -855
-999 -350
-999 -174
-999 -51
-999 -43
-999 235
-999 465
-999 530
-998 -997
-998 -311
-998 21
-998 44
-998 182
-997 -313
-997 -195
-997 -13
-997 412
-997 425
-996 -542
-996 -348
-996 -126
-996 -59
-996 -40
-996 84
-...

output:

5.91151100390402639562
3.74386851513771157229
2.53848285831534692392
2.15996735885788737619
4.29503770957234465300
4.77167447479618189732
4.68240781260193550395
5.07898439417457403522
1.60080182141066384993
3.34040254563670480081
3.36879252825034880559
2.11301602823006184906
4.85539941013267029035
4...

result:

ok 20 numbers

Test #10:

score: 0
Accepted
time: 22ms
memory: 6976kb

input:

1
166347 18723
-1000 -979
-1000 -975
-1000 -928
-1000 -914
-1000 -898
-1000 -889
-1000 -876
-1000 -873
-1000 -858
-1000 -840
-1000 -838
-1000 -801
-1000 -783
-1000 -744
-1000 -738
-1000 -733
-1000 -713
-1000 -712
-1000 -695
-1000 -689
-1000 -680
-1000 -675
-1000 -671
-1000 -646
-1000 -643
-1000 -608...

output:

0.85144917898051586391

result:

ok found '0.8514492', expected '0.8514492', error '0.0000000'

Test #11:

score: 0
Accepted
time: 24ms
memory: 6816kb

input:

1
154903 84960
-1000 -979
-1000 -965
-1000 -956
-1000 -945
-1000 -920
-1000 -901
-1000 -878
-1000 -860
-1000 -858
-1000 -709
-1000 -693
-1000 -648
-1000 -619
-1000 -602
-1000 -579
-1000 -474
-1000 -473
-1000 -454
-1000 -443
-1000 -427
-1000 -407
-1000 -403
-1000 -384
-1000 -351
-1000 -279
-1000 -244...

output:

3.53892668538316623739

result:

ok found '3.5389267', expected '3.5389267', error '0.0000000'

Test #12:

score: 0
Accepted
time: 21ms
memory: 6772kb

input:

1
158037 96343
-1000 -1000
-1000 -905
-1000 -881
-1000 -833
-1000 -804
-1000 -803
-1000 -782
-1000 -775
-1000 -765
-1000 -759
-1000 -756
-1000 -748
-1000 -722
-1000 -674
-1000 -669
-1000 -630
-1000 -610
-1000 -573
-1000 -443
-1000 -411
-1000 -409
-1000 -403
-1000 -388
-1000 -366
-1000 -349
-1000 -33...

output:

3.97202877832588052698

result:

ok found '3.9720288', expected '3.9720288', error '0.0000000'

Test #13:

score: 0
Accepted
time: 27ms
memory: 4148kb

input:

10000
17 12
-853202371 684059854
-659446544 -924219854
-418025687 117998679
-399757126 -365708913
-331597239 -270896799
-204989763 869548983
-118492298 963842298
-77481232 672198731
45930201 -58234380
52605147 -900097542
78371985 940503934
235210685 595759114
391284089 234315077
416229789 -827244230...

output:

5.39852511003435253656
5.37390787485642285048
1.17357817287416188456
1.54436525950838587917
3.77828864940306852205
3.57047158685250476395
6.28297485883615891566
5.09592520281510008573
2.98757824655085046928
2.30556650580152933117
3.39078416418203509863
5.78547323812813285571
4.81096361226396496136
0...

result:

ok 10000 numbers

Test #14:

score: 0
Accepted
time: 28ms
memory: 4252kb

input:

1000
133 108
-994106086 710243426
-991027749 -548437545
-983318226 -917527783
-943673956 -368162275
-935819096 616077188
-928022346 487569673
-924213856 -369318351
-914827619 426646545
-883935180 590882141
-870015071 -270471333
-834927107 -211343853
-829266515 354007200
-788041913 -60481736
-7822837...

output:

5.74280179214319552727
1.91536423984179382529
3.80434579810800688193
1.79191627053112978452
3.16952067063520326329
6.07864621461560172833
3.78606745951064116440
3.66596907268785621170
6.22658345297044490962
5.90215219261038992471
5.94431570929567598682
0.71516768704310207383
3.83157425297719989032
1...

result:

ok 1000 numbers

Test #15:

score: 0
Accepted
time: 29ms
memory: 4204kb

input:

100
1367 924
-999416811 990355566
-997656126 346133696
-997071616 -657387469
-996176051 12622726
-995720693 334093112
-995478093 891631278
-994503890 341858449
-994297596 499383911
-993234202 533518057
-991636838 -4170504
-990563582 -407186200
-989454027 653116272
-989132124 -780605454
-988073521 -1...

output:

4.50515349061768866079
2.71255893262747793671
5.83967858098196668237
6.02297711145261516208
0.46160604310141639672
0.98699123321252280050
1.32197084883432314228
1.92584174583805944891
5.50860835334990994738
4.64635533129787869910
2.28767741020770642990
2.18487258779632975703
4.80940919180683845724
0...

result:

ok 100 numbers

Test #16:

score: 0
Accepted
time: 32ms
memory: 4556kb

input:

10
13806 4955
-999669776 933068103
-999542354 721337508
-999499427 357140594
-999429088 -925180511
-999334813 -145726169
-999291694 -886327684
-999281647 811188099
-999145269 860687107
-998961821 -979442436
-998769313 446186367
-998591455 658309173
-998539751 -569480843
-998479467 279850955
-9984754...

output:

2.41708046803397813562
6.16119222907872643447
3.96002037684223529013
3.99436179290459270064
2.55155083615552058518
0.52272383678099898496
4.09784382785422884865
6.21038266315892961700
5.98172802925396496221
0.77722368589060053523

result:

ok 10 numbers

Test #17:

score: 0
Accepted
time: 22ms
memory: 5812kb

input:

1
112596 94970
-999980219 399324466
-999932413 952114487
-999894556 -951211102
-999891030 -996222974
-999864824 412806264
-999853190 -269700371
-999845814 -23906803
-999841507 -459154880
-999825178 716247149
-999761774 -154047106
-999729655 -171480333
-999709604 -666447277
-999704754 -22442485
-9996...

output:

5.44259387934385152619

result:

ok found '5.4425939', expected '5.4425939', error '0.0000000'

Test #18:

score: 0
Accepted
time: 32ms
memory: 7120kb

input:

1
161568 13252
-999991243 -113889211
-999976572 -361096764
-999970140 -505012445
-999960654 600963873
-999959339 -269932510
-999956568 734634576
-999941447 716485764
-999940305 64397798
-999939982 746532931
-999939921 995002380
-999932747 185078659
-999927136 585216518
-999914684 898656539
-99990452...

output:

0.64247459068649703795

result:

ok found '0.6424746', expected '0.6424746', error '0.0000000'

Test #19:

score: 0
Accepted
time: 38ms
memory: 7656kb

input:

1
186192 126483
-999998234 974001047
-999976292 -133179660
-999967957 112862981
-999957851 70030467
-999951528 743907713
-999931316 66002112
-999907988 888991267
-999905412 470798211
-999903986 -103943462
-999900422 255729004
-999898174 917068198
-999884392 -183592605
-999880179 -650076162
-99987469...

output:

4.40124568411900973786

result:

ok found '4.4012457', expected '4.4012457', error '0.0000000'

Test #20:

score: 0
Accepted
time: 20ms
memory: 4212kb

input:

1000
133 9
-10 -839744900
-10 -620593257
-10 -322048342
-10 578093727
-10 898998949
-9 -833794004
-9 -704882916
-9 -570204575
-9 -506146571
-9 -109555290
-9 309734100
-9 396668416
-8 -928874025
-8 376566668
-8 596463598
-8 600491164
-8 894775141
-7 -281322833
-7 49984651
-7 154512939
-7 205573228
-7...

output:

3.14159258288777998303
6.28318524821367851985
3.14159261442497861339
3.14159117408144172856
6.28318527029175299958
6.28318529531632741225
3.14159264922942593756
6.28318530367009930870
3.14159264016155814758
6.28318525067592847932
6.28318528164825718108
3.14159275918694014251
3.14159264537055671340
3...

result:

ok 1000 numbers

Test #21:

score: 0
Accepted
time: 19ms
memory: 4808kb

input:

5
23120 8224
-10 -999575056
-10 -997485895
-10 -995458183
-10 -986953157
-10 -985268102
-10 -983223383
-10 -980910524
-10 -980404283
-10 -973605147
-10 -972441960
-10 -972440422
-10 -969122114
-10 -965754004
-10 -964812113
-10 -964558462
-10 -963159275
-10 -962972564
-10 -962085557
-10 -961552443
-1...

output:

3.14159264235138913079
3.14159263124244247933
3.14159260680078267214
3.14159264939531901462
6.28318527220692235602

result:

ok 5 numbers

Test #22:

score: 0
Accepted
time: 11ms
memory: 5504kb

input:

1
99995 60000
1 100001
1 100002
1 100003
1 100004
1 100005
1 100006
1 100007
1 100008
1 100009
1 100010
1 100011
1 100012
1 100013
1 100014
1 100015
1 100016
1 100017
1 100018
1 100019
1 100020
1 100021
1 100022
1 100023
1 100024
1 100025
1 100026
1 100027
1 100028
1 100029
1 100030
1 100031
1 10003...

output:

6.28318530690181731302

result:

ok found '6.2831853', expected '6.2831853', error '0.0000000'

Extra Test:

score: 0
Extra Test Passed