QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#469075#7229. LinespropaneAC ✓1491ms7824kbC++202.4kb2024-07-09 13:11:132024-07-09 13:11:13

Judging History

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

  • [2024-07-09 13:11:13]
  • 评测
  • 测评结果:AC
  • 用时:1491ms
  • 内存:7824kb
  • [2024-07-09 13:11:13]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<cmath>
#include<numeric>
#include<iomanip>
#include<algorithm>
using namespace std;
using LL = long long;

const int maxn = 1e5 + 5;
int tr[maxn];

int lowbit(int x){
    return x & -x;
}

void modify(int x, int v){
    while(x < maxn){
        tr[x] += v;
        x += lowbit(x);
    }
}

int query(int x){
    int ans = 0;
    while(x){
        ans += tr[x];
        x -= lowbit(x);
    }
    return ans;
}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);

    int n;
    cin >> n;
    vector<pair<int, int> > p(n);
    vector<int> nums, q(n);
    for(int i = 0; i < n; i++){
        cin >> p[i].first >> p[i].second;
        nums.push_back(p[i].second);
    }
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    for(int i = 0; i < n; i++){
        q[i] = lower_bound(nums.begin(), nums.end(), p[i].second) - nums.begin() + 1;
    }

    const double pi = numbers::pi;

    auto check = [&](double a){
        double cosa = cos(a), sina = sin(a);
        vector<pair<double, int> > pt(n);
        vector<double> nums;
        nums.reserve(n);
        for(int i = 0; i < n; i++){
            auto [x, y] = p[i];
            pt[i] = {x * sina + -y * cosa, q[i]};
            nums.push_back(pt[i].second);
        }
        sort(pt.begin(), pt.end(), [&](auto &&a, auto &&b){
            if (a.first != b.first) return a.first > b.first;
            return a.second > b.second;
        });
        LL ans = 0;
        memset(tr, 0, sizeof tr);
        for(int i = 0; i < n; i++){
            auto [x, y] = pt[i];
            ans += i - query(y - 1);
            modify(y, 1);
        }
        return ans;
    };

    auto get = [&](LL cnt){

        double l = 0, r = pi;
        for(int _ = 0; _ < 70; _++){
            double mid = (l + r) / 2;
            if (check(mid) >= cnt) r = mid;
            else l = mid;
        }
        return r;
    };

    LL tot = 1LL * n * (n - 1) / 2;
    if (tot % 2 == 1){
        cout << get(tot / 2 + 1) << '\n';
    }
    else{
        cout << (get(tot / 2) + get(tot / 2 + 1)) / 2 << '\n';
    }

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4552kb

input:

3
0 0
0 1
1 0

output:

1.57079632679489678004

result:

ok found '1.570796327', expected '1.570796327', error '0.000000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 4488kb

input:

4
0 0
0 1
1 0
1 1

output:

1.17809724509617264054

result:

ok found '1.178097245', expected '1.178097245', error '0.000000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 4496kb

input:

3
0 0
0 1000000000
1 0

output:

1.57079632679489678004

result:

ok found '1.570796327', expected '1.570796327', error '0.000000000'

Test #4:

score: 0
Accepted
time: 1ms
memory: 4488kb

input:

3
0 0
1 0
2 0

output:

0.00000000000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 4392kb

input:

3
5 -2
-5 -4
-4 4

output:

1.44644133224813509209

result:

ok found '1.446441332', expected '1.446441332', error '0.000000000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 4424kb

input:

3
0 4
-3 -1
-4 4

output:

1.03037682652431250574

result:

ok found '1.030376827', expected '1.030376827', error '0.000000000'

Test #7:

score: 0
Accepted
time: 1ms
memory: 4336kb

input:

3
0 -1
3 -3
-4 1

output:

2.62244653934327054401

result:

ok found '2.622446539', expected '2.622446539', error '0.000000000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 4460kb

input:

3
-5 -3
-3 0
3 5

output:

0.78539816339744839002

result:

ok found '0.785398163', expected '0.785398163', error '0.000000000'

Test #9:

score: 0
Accepted
time: 1ms
memory: 4508kb

input:

3
-5 3
-1 -2
5 -3

output:

2.60117315331920906374

result:

ok found '2.601173153', expected '2.601173153', error '0.000000000'

Test #10:

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

input:

3
-2 0
-3 3
1 -2

output:

2.24553726901844941111

result:

ok found '2.245537269', expected '2.245537269', error '0.000000000'

Test #11:

score: 0
Accepted
time: 1ms
memory: 4396kb

input:

3
-2 -1
-3 2
1 -3

output:

2.24553726901844941111

result:

ok found '2.245537269', expected '2.245537269', error '0.000000000'

Test #12:

score: 0
Accepted
time: 1ms
memory: 4396kb

input:

3
3 -3
1 -1
0 2

output:

2.11121582706548105435

result:

ok found '2.111215827', expected '2.111215827', error '0.000000000'

Test #13:

score: 0
Accepted
time: 1ms
memory: 4468kb

input:

3
0 -3
2 0
-3 0

output:

0.98279372324732905408

result:

ok found '0.982793723', expected '0.982793723', error '0.000000000'

Test #14:

score: 0
Accepted
time: 1ms
memory: 4504kb

input:

5
1 -3
0 -3
2 2
-3 3
-3 -2

output:

1.80262013129529963251

result:

ok found '1.802620131', expected '1.802620131', error '0.000000000'

Test #15:

score: 0
Accepted
time: 1ms
memory: 4468kb

input:

5
-3 -2
2 -2
1 -2
1 -1
2 0

output:

0.58295227025490659045

result:

ok found '0.582952270', expected '0.582952270', error '0.000000000'

Test #16:

score: 0
Accepted
time: 1ms
memory: 4396kb

input:

50
-3 -3
5 -5
0 -5
-5 2
4 -4
2 0
2 1
4 4
4 1
-4 4
5 -2
1 -2
-2 -5
1 1
-5 1
3 0
-2 -3
-1 1
-2 3
1 -4
-3 -4
-5 -3
-5 -2
-4 3
0 -3
-2 4
5 0
-4 5
0 3
1 4
4 -2
-5 -5
2 2
0 -4
-3 -2
-3 3
5 1
-5 -1
1 -1
3 -1
3 -5
-1 4
-2 -1
2 -1
4 -3
-3 4
1 -5
-2 -4
4 -1
-4 -3

output:

1.57079632679489655800

result:

ok found '1.570796327', expected '1.570796327', error '0.000000000'

Test #17:

score: 0
Accepted
time: 1ms
memory: 4392kb

input:

50
4 4
2 1
-2 1
5 -3
-4 -1
-1 2
-4 2
-2 4
0 -1
5 -4
2 -4
-5 4
-5 -3
-1 -4
-4 5
5 2
-5 -4
-3 4
4 2
4 -4
-3 -5
1 -4
2 5
-5 2
-5 0
-1 3
0 -4
3 -1
4 -2
-4 4
3 5
5 4
-5 -5
0 4
2 0
-2 3
5 -2
3 -2
0 0
1 4
-1 5
-2 -3
2 -1
-4 -3
1 -1
3 0
0 -5
3 3
1 3
3 -3

output:

1.57079632679489655800

result:

ok found '1.570796327', expected '1.570796327', error '0.000000000'

Test #18:

score: 0
Accepted
time: 1ms
memory: 4416kb

input:

50
442366208 279138083
-184561367 198541207
823405894 -564413219
114448377 768487602
821151082 67547042
-590952942 632915301
-84600698 238839968
-91932460 -515319949
423477410 385540707
691437964 288336391
-698919416 -197720761
438870279 -237612652
-881837701 -262857085
-888782888 -342919408
-530160...

output:

1.41864409413216030487

result:

ok found '1.418644094', expected '1.418644094', error '0.000000000'

Test #19:

score: 0
Accepted
time: 1ms
memory: 4480kb

input:

50
816110770 -689704132
494898871 528573081
166680604 515808141
582252599 -643183741
-145562034 486547080
980124566 -330599192
748101806 -46206986
-501110119 165526141
-720565034 -327594840
31430157 726724609
933586752 -541260952
7341547 -388059679
-547192977 928287659
-355113178 817115401
4908934 -...

output:

1.65611710221994301584

result:

ok found '1.656117102', expected '1.656117102', error '0.000000000'

Test #20:

score: 0
Accepted
time: 1469ms
memory: 7788kb

input:

100000
-150948623 524048786
15875754 245984095
-680102685 -996037369
-312145822 195412711
-125286014 -425984089
567533629 -568729767
742167809 637057223
940696884 755774175
453965564 -895474249
-251790074 -207350084
-35145288 827732799
-102503325 834935376
-106803294 -881188847
-115569148 929149793
...

output:

1.56764571644878492052

result:

ok found '1.567645716', expected '1.567645716', error '0.000000000'

Test #21:

score: 0
Accepted
time: 1168ms
memory: 7068kb

input:

80000
-587936709 929197030
816737335 627407406
-637765108 -922560549
195018519 -727622801
-241427948 -327364749
101056395 -109287213
630367532 419032556
-909404639 247331311
-534804709 -71253478
-386848538 -884231482
-347799932 -459070134
-383728988 -597639650
52319706 -436484000
-631234444 -1095229...

output:

1.56480298085651337026

result:

ok found '1.564802981', expected '1.564802981', error '0.000000000'

Test #22:

score: 0
Accepted
time: 0ms
memory: 4488kb

input:

4
-3 -4
-5 -4
2 -1
-3 -2

output:

0.47265564327783382570

result:

ok found '0.472655643', expected '0.472655643', error '0.000000000'

Test #23:

score: 0
Accepted
time: 1ms
memory: 4420kb

input:

10
-3 -7
-5 9
-1 6
-8 2
-7 7
-7 9
4 -1
-5 8
-6 -3
5 1

output:

1.70334785909157071515

result:

ok found '1.703347859', expected '1.703347859', error '0.000000000'

Test #24:

score: 0
Accepted
time: 1ms
memory: 4392kb

input:

3
-1000000000 0
1000000000 0
1000000000 1

output:

0.00000000050000000000

result:

ok found '0.000000001', expected '0.000000000', error '0.000000000'

Test #25:

score: 0
Accepted
time: 1ms
memory: 4548kb

input:

3
-1000000000 0
1000000000 0
1000000000 3

output:

0.00000000150000000000

result:

ok found '0.000000001', expected '0.000000001', error '0.000000000'

Test #26:

score: 0
Accepted
time: 0ms
memory: 4404kb

input:

3
-1000000000 0
1000000000 0
1000000000 2

output:

0.00000000100000000000

result:

ok found '0.000000001', expected '0.000000001', error '0.000000000'

Test #27:

score: 0
Accepted
time: 0ms
memory: 4344kb

input:

3
-1000000000 0
1000000000 0
1000000000 5

output:

0.00000000250000000000

result:

ok found '0.000000003', expected '0.000000002', error '0.000000000'

Test #28:

score: 0
Accepted
time: 1483ms
memory: 7696kb

input:

99996
733545312 -23346396
-795397579 -404874879
-503473099 346027613
-271528713 -541325642
-669874444 -941994460
-674798430 409694556
487315158 -533882734
246335663 -544516742
-492477912 100172425
-654705047 -45422316
-165735959 -730361490
-641262284 -149381708
642195259 -244019849
21537641 -5325330...

output:

1.57073848896030998645

result:

ok found '1.570738489', expected '1.570738489', error '0.000000000'

Test #29:

score: 0
Accepted
time: 1490ms
memory: 7792kb

input:

100000
-569987404 -522495344
77828992 -662077558
-751319779 -938754614
676233529 -390989412
-342796279 193802311
-910748645 329001647
746314690 908001266
-806922069 -61518020
190012289 -58380902
-215639185 159517877
-12714720 460330830
401525335 -85070032
178844347 651458858
20684297 -691741658
-110...

output:

1.57240249188474812136

result:

ok found '1.572402492', expected '1.572402492', error '0.000000000'

Test #30:

score: 0
Accepted
time: 1478ms
memory: 7644kb

input:

100000
671546196 228818010
-138266629 -168233695
-323825826 334459800
216860157 -420208747
672003460 208806122
-809177211 -456068361
477663340 -650382451
-31912342 -308752646
-88781777 441847309
-921419665 -138650701
426257808 981991375
206212481 68641036
-103615306 283968886
-478941139 -362861676
2...

output:

1.56725681704208419376

result:

ok found '1.567256817', expected '1.567256817', error '0.000000000'

Test #31:

score: 0
Accepted
time: 760ms
memory: 7696kb

input:

99999
720191241 515523232
-327632871 233538461
-512554358 300865696
945279418 -948967513
905326284 -195443076
-950976185 551550213
93457422 -563142084
-593586533 -534241503
97255263 704845131
-159218457 688468773
-324735405 -271552899
215928797 -182292140
-572215716 -15793098
-385927186 455428739
91...

output:

1.57400670955857391320

result:

ok found '1.574006710', expected '1.574006710', error '0.000000000'

Test #32:

score: 0
Accepted
time: 1413ms
memory: 7712kb

input:

100000
984248694 0
614763735 0
203383912 0
862359296 0
471173801 0
-845317945 0
-675081068 0
774777131 0
-981022826 0
-659358460 0
-374324456 0
-265414003 0
-471863230 0
69564448 0
53101464 0
379471890 0
-105773755 0
614481264 0
-677989401 0
475617349 0
615133202 0
-879495987 0
-147413262 0
63532743...

output:

0.00000000000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #33:

score: 0
Accepted
time: 1411ms
memory: 7604kb

input:

100000
57050460 0
-375026139 0
-820386623 0
-99980585 0
-512640358 0
167544347 0
-232780265 0
-373340677 0
58293973 0
-784457940 0
383364961 0
487333353 0
609709989 0
666053328 0
-383548055 0
910405928 0
149861137 0
-254137401 0
-577038938 0
-84360914 0
573266580 0
859984770 0
-71001073 0
867939952 ...

output:

0.00000000000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #34:

score: 0
Accepted
time: 1423ms
memory: 7772kb

input:

100000
876809794 -438404747
394286770 -197143235
-367448514 183724407
-383434666 191717483
936480596 -468240148
-40502056 20251178
725524068 -362761884
181615020 -90807360
-477458542 238729421
922627006 -461313353
-106096964 53048632
431977902 -215988801
-164082662 82041481
-686224656 343112478
-915...

output:

2.67794504458898741106

result:

ok found '2.677945045', expected '2.677945045', error '0.000000000'

Test #35:

score: 0
Accepted
time: 1442ms
memory: 7824kb

input:

100000
-154037240 1510270
362293900 -3551800
2089162 -20381
-717258188 7032044
-424230650 4159225
-556396946 5454973
-886314620 8689460
-265795274 2605937
-930613526 9123763
-594000164 5823632
927217330 -9090265
-325966706 3195853
368042926 -3608163
675258664 -6620082
-772772504 7576302
392022922 -3...

output:

3.13178904611049757634

result:

ok found '3.131789046', expected '3.131789046', error '0.000000000'

Test #36:

score: 0
Accepted
time: 1422ms
memory: 7748kb

input:

100000
412444110 -457155
-684758612 759256
479239014 -531207
390243184 -432542
453834184 -503042
-680452464 754482
866004888 -959994
483779682 -536241
-149556912 165906
937503722 -1039261
334160432 -370366
-855163550 948175
-900129152 998026
-638461658 707929
90074722 -99761
-264980440 293870
-59571...

output:

3.14048400659389459477

result:

ok found '3.140484007', expected '3.140484007', error '0.000000000'

Test #37:

score: 0
Accepted
time: 1425ms
memory: 7740kb

input:

100000
796270214 1
-951846498 0
217668093 -2
-154910102 0
546144954 2
-886725978 -1
607295668 -1
81163900 0
842244991 0
394451733 2
-202184886 0
-296096210 0
550660940 -1
-177897556 1
-114486127 0
-419083768 1
843168056 1
-889488949 -2
-276903726 0
-682069189 -2
629500056 0
-207727363 2
-580841513 -...

output:

0.00000000730553027254

result:

ok found '0.000000007', expected '0.000000007', error '0.000000000'

Test #38:

score: 0
Accepted
time: 1423ms
memory: 7716kb

input:

100000
-253706492 2
-226875621 2
362330838 2
-795605493 2
-215290842 -2
707063086 0
-873673230 -2
-481532653 -1
-830595165 1
748511407 0
809118374 2
1935598 0
-466786749 2
280720810 0
-568005292 2
42343361 2
-484237657 0
-411967860 -2
-364775056 -2
918375933 0
-627927595 -1
-914082092 -1
-236146640 ...

output:

0.00000000726321615720

result:

ok found '0.000000007', expected '0.000000007', error '0.000000000'

Test #39:

score: 0
Accepted
time: 1491ms
memory: 7644kb

input:

100000
934702833 -467351271
-131493362 65746831
913964656 -456982181
627793697 -313896700
-638371333 319185816
976407872 -488203783
-968962292 484481297
565975688 -282987694
-202963342 101481827
-811264552 405632422
-768479282 384239788
115616122 -57807913
-583740418 291870360
-291751130 145875716
1...

output:

2.67794504458898741106

result:

ok found '2.677945045', expected '2.677945045', error '0.000000000'

Test #40:

score: 0
Accepted
time: 1474ms
memory: 7640kb

input:

100000
-668200264 6551087
86496002 -847902
-871928849 8548421
-136205907 1335452
-402219969 3943437
-259323369 2542482
-467469268 4583131
-840900142 8244217
204026622 -2000159
724703160 -7104827
-851573316 8348862
-53404139 523674
-624909125 6126662
-823741703 8076002
-738369842 7239018
101639630 -9...

output:

3.13178904611049757634

result:

ok found '3.131789046', expected '3.131789046', error '0.000000000'

Test #41:

score: 0
Accepted
time: 1449ms
memory: 7640kb

input:

100000
595966829 -660620
-51714261 57430
991615602 -1099248
-863804708 957752
902860607 -1000854
772085940 -855873
-55307834 61418
870845924 -965357
-466679365 517486
638883092 -708194
512483125 -568062
-375955304 416905
273537917 -303162
685640068 -760038
-59830465 66428
248798757 -275725
-65529026...

output:

3.14048400659389459477

result:

ok found '3.140484007', expected '3.140484007', error '0.000000000'

Test #42:

score: 0
Accepted
time: 1426ms
memory: 7636kb

input:

100000
140 20
2 -114
152 -60
-82 123
-78 -42
-64 173
155 -18
-159 -124
88 6
76 -80
-111 -123
-49 150
155 -125
-107 161
-66 -133
67 -49
-17 -143
32 91
87 -104
-132 -170
84 65
87 -164
114 -56
24 -40
59 -34
24 -22
38 -57
-169 10
139 132
44 11
66 -100
-85 176
13 -173
-88 111
-45 -95
9 173
-141 74
-71 15...

output:

1.56629185275632876184

result:

ok found '1.566291853', expected '1.566291853', error '0.000000000'

Test #43:

score: 0
Accepted
time: 1491ms
memory: 7744kb

input:

100000
-79 -25
-117 178
-70 221
-291 71
137 117
-234 -236
138 -47
-242 -167
-126 26
-39 49
240 -99
215 -174
106 -46
201 -180
172 -177
121 205
172 -115
63 25
-194 168
-295 -230
40 -91
190 230
25 -290
-124 114
176 271
-60 160
26 134
254 -57
-256 -4
153 -254
244 107
248 118
280 205
-148 115
-226 78
64 ...

output:

1.57079632679489655800

result:

ok found '1.570796327', expected '1.570796327', error '0.000000000'

Test #44:

score: 0
Accepted
time: 1454ms
memory: 7636kb

input:

100000
74068734 -67184987
-73589858 -67709177
-63969660 -76862751
-90718064 42074133
-85849482 51282222
99386751 -11057737
99242656 -12283938
44456013 89574900
-42225124 -90647883
-85086246 52538849
-39587889 91830272
-88887165 45815628
82700993 -56218730
-91952953 39302090
6987486 99755576
99035725...

output:

1.57078062106102800399

result:

ok found '1.570780621', expected '1.570780621', error '0.000000000'

Test #45:

score: 0
Accepted
time: 738ms
memory: 7748kb

input:

99999
400813117 -805821844
874374859 -213233688
33553856 899374304
853659607 285070648
884703587 -165225789
757339336 -486248012
-522420355 -732855355
765731649 472921813
-864587019 -249978569
-759849679 482315731
-815400632 -380948563
-805758874 -400939690
-588492236 680938240
-553669423 -709542225...

output:

1.57079632679489633595

result:

ok found '1.570796327', expected '1.570796327', error '0.000000000'

Test #46:

score: 0
Accepted
time: 736ms
memory: 7672kb

input:

99999
99957306 -2955708
-9788208 99519803
-31843316 -94794095
-62763244 -77850073
80074973 -59901141
-84942988 -52768440
-41307853 -91068987
-31530448 -94898623
327725 99999566
41438558 91010697
73435383 -67877667
96362459 26729655
98488617 -17325871
-99719603 7470125
-17485840 -98459081
21842916 97...

output:

1.57078061758294196260

result:

ok found '1.570780618', expected '1.570780618', error '0.000000000'

Test #47:

score: 0
Accepted
time: 1469ms
memory: 7712kb

input:

100000
-94881770 31583126
44754159 -89425361
87229737 -48896753
77708105 62941177
90472101 42601668
-91109174 -41219142
-53431299 -84527608
98536311 -17046435
-54051247 84134535
99973514 2306724
-54541944 83817259
-40120830 91599640
99916841 4080796
8127849 -99668151
91015903 -41425121
91544457 4024...

output:

1.57078027738696590632

result:

ok found '1.570780277', expected '1.570780277', error '0.000000000'

Test #48:

score: 0
Accepted
time: 2ms
memory: 4468kb

input:

201
-100 10000
-99 9801
-98 9604
-97 9409
-96 9216
-95 9025
-94 8836
-93 8649
-92 8464
-91 8281
-90 8100
-89 7921
-88 7744
-87 7569
-86 7396
-85 7225
-84 7056
-83 6889
-82 6724
-81 6561
-80 6400
-79 6241
-78 6084
-77 5929
-76 5776
-75 5625
-74 5476
-73 5329
-72 5184
-71 5041
-70 4900
-69 4761
-68 46...

output:

1.56542003450918776331

result:

ok found '1.565420035', expected '1.565420035', error '0.000000000'

Test #49:

score: 0
Accepted
time: 201ms
memory: 6412kb

input:

62003
-31001 961062001
-31000 961000000
-30999 960938001
-30998 960876004
-30997 960814009
-30996 960752016
-30995 960690025
-30994 960628036
-30993 960566049
-30992 960504064
-30991 960442081
-30990 960380100
-30989 960318121
-30988 960256144
-30987 960194169
-30986 960132196
-30985 960070225
-3098...

output:

1.57078013324964538278

result:

ok found '1.570780133', expected '1.570780133', error '0.000000000'