QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#469072 | #7229. Lines | propane | AC ✓ | 3721ms | 7092kb | C++20 | 2.3kb | 2024-07-09 13:06:02 | 2024-07-09 13:06:02 |
Judging History
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);
for(int i = 0; i < n; i++){
cin >> p[i].first >> p[i].second;
}
const double pi = numbers::pi;
auto check = [&](double a){
double cosa = cos(a), sina = sin(a);
vector<pair<int, double> > pt(n);
vector<double> nums;
nums.reserve(n);
for(int i = 0; i < n; i++){
auto [x, y] = p[i];
pt[i] = {y, x * sina + -y * cosa};
nums.push_back(pt[i].second);
}
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
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];
int t = lower_bound(nums.begin(), nums.end(), y) - nums.begin() + 1;
ans += i - query(t - 1);
modify(t, 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: 4392kb
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: 0ms
memory: 4480kb
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: 1ms
memory: 4480kb
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: 4428kb
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: 4548kb
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: 4428kb
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: 0ms
memory: 4540kb
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: 1ms
memory: 4472kb
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: 4400kb
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: 4440kb
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: 4348kb
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: 4456kb
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: 4372kb
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: 4460kb
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: 0ms
memory: 4436kb
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: 4372kb
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: 4420kb
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: 4480kb
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: 4488kb
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: 3692ms
memory: 7080kb
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: 2886ms
memory: 6348kb
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: 1ms
memory: 4472kb
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: 4496kb
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: 4372kb
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: 0ms
memory: 4456kb
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: 1ms
memory: 4424kb
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: 1ms
memory: 4484kb
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: 3696ms
memory: 7080kb
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: 3717ms
memory: 6984kb
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: 3721ms
memory: 7036kb
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: 1862ms
memory: 7044kb
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: 2967ms
memory: 6868kb
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: 2954ms
memory: 7024kb
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: 2458ms
memory: 6968kb
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: 2613ms
memory: 6984kb
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: 2729ms
memory: 6892kb
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: 3160ms
memory: 7032kb
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: 3164ms
memory: 6988kb
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: 2886ms
memory: 6864kb
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: 3279ms
memory: 6968kb
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: 3295ms
memory: 6872kb
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: 3565ms
memory: 7092kb
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: 3436ms
memory: 6968kb
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: 3022ms
memory: 6868kb
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: 1520ms
memory: 6864kb
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: 1519ms
memory: 7040kb
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: 3039ms
memory: 7036kb
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: 3ms
memory: 4492kb
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: 716ms
memory: 5852kb
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'