QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#179288 | #7229. Lines | PhantomThreshold# | AC ✓ | 2287ms | 19028kb | C++20 | 1.9kb | 2023-09-14 20:18:26 | 2023-09-14 20:18:27 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const int maxn = 105000;
const long double pi = acos(-1);
const long double eps = 1e-12;
//const long double inf = 2e9;
int n;
struct node
{
int x,y;
//friend long double operator *(const node &k1,const node &k2){ return k1.x*k2.x+k1.y*k2.y; }
}p[maxn];
pair<long double,int>a[maxn];
pair<long double,int>t[maxn];
int s[maxn];
void init()
{
for(int i=1;i<=n;i++) s[i]=0;
}
void add(int x)
{
for(;x<=n;x+=lowbit(x)) s[x]++;
}
int query(int x)
{
int re=0;
for(;x;x-=lowbit(x)) re+=s[x];
return re;
}
int base;
int calc(long double mid)
{
mid=mid-pi/2;
long double k= tan(mid);
for(int i=1;i<=n;i++)
{
a[i]=make_pair( p[i].x, 0 );
t[i]=make_pair( p[i].y-k*p[i].x,i );
}
sort(t+1,t+n+1);
for(int i=1;i<=n;i++) a[ t[i].second ].second=i;
sort(a+1,a+n+1);
init();
int ret=0;
for(int i=1;i<=n;)
{
int j=i;
while(j<=n&&a[i].first==a[j].first)
{
ret+= (i-1)-query(a[j].second);
j++;
}
while(i<j)
{
add(a[i].second);
i++;
}
}
return base+ret;
}
long double get_kth(int k)
{
long double l=0,r= pi-eps;
while(r-l>eps)
{
long double mid=(l+r)/2;
int num= calc(mid);
if(num>=k) r=mid;
else l=mid;
}
return l;
}
signed main()
{
ios_base::sync_with_stdio(false); ////////////////////////////////////////
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>p[i].x>>p[i].y;
swap(p[i].x,p[i].y);
p[i].y=-p[i].y;
}
base=0;
map<int,int>mp;
for(int i=1;i<=n;i++)
{
if(mp.count(p[i].x)>0) base+=mp[p[i].x];
mp[p[i].x]++;
}
int N= n*(n-1)/2;
long double ans;
if(N%2==0) ans= ( get_kth(N/2)+get_kth(N/2+1) )/2;
else ans= get_kth(N/2+1);
cout<<fixed<<setprecision(12)<<ans<<endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 9784kb
input:
3 0 0 0 1 1 0
output:
1.570796326794
result:
ok found '1.570796327', expected '1.570796327', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 7736kb
input:
4 0 0 0 1 1 0 1 1
output:
1.178097245096
result:
ok found '1.178097245', expected '1.178097245', error '0.000000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 7820kb
input:
3 0 0 0 1000000000 1 0
output:
1.570796326794
result:
ok found '1.570796327', expected '1.570796327', error '0.000000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 9788kb
input:
3 0 0 1 0 2 0
output:
0.000000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #5:
score: 0
Accepted
time: 2ms
memory: 9824kb
input:
3 5 -2 -5 -4 -4 4
output:
1.446441332248
result:
ok found '1.446441332', expected '1.446441332', error '0.000000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 7828kb
input:
3 0 4 -3 -1 -4 4
output:
1.030376826524
result:
ok found '1.030376827', expected '1.030376827', error '0.000000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 5696kb
input:
3 0 -1 3 -3 -4 1
output:
2.622446539343
result:
ok found '2.622446539', expected '2.622446539', error '0.000000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 9796kb
input:
3 -5 -3 -3 0 3 5
output:
0.785398163397
result:
ok found '0.785398163', expected '0.785398163', error '0.000000000'
Test #9:
score: 0
Accepted
time: 1ms
memory: 5708kb
input:
3 -5 3 -1 -2 5 -3
output:
2.601173153319
result:
ok found '2.601173153', expected '2.601173153', error '0.000000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 9784kb
input:
3 -2 0 -3 3 1 -2
output:
2.245537269018
result:
ok found '2.245537269', expected '2.245537269', error '0.000000000'
Test #11:
score: 0
Accepted
time: 2ms
memory: 9972kb
input:
3 -2 -1 -3 2 1 -3
output:
2.245537269018
result:
ok found '2.245537269', expected '2.245537269', error '0.000000000'
Test #12:
score: 0
Accepted
time: 2ms
memory: 9776kb
input:
3 3 -3 1 -1 0 2
output:
2.111215827065
result:
ok found '2.111215827', expected '2.111215827', error '0.000000000'
Test #13:
score: 0
Accepted
time: 2ms
memory: 9788kb
input:
3 0 -3 2 0 -3 0
output:
0.982793723247
result:
ok found '0.982793723', expected '0.982793723', error '0.000000000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 9732kb
input:
5 1 -3 0 -3 2 2 -3 3 -3 -2
output:
1.802620131295
result:
ok found '1.802620131', expected '1.802620131', error '0.000000000'
Test #15:
score: 0
Accepted
time: 0ms
memory: 7752kb
input:
5 -3 -2 2 -2 1 -2 1 -1 2 0
output:
0.582952270255
result:
ok found '0.582952270', expected '0.582952270', error '0.000000000'
Test #16:
score: 0
Accepted
time: 2ms
memory: 9868kb
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.570796326794
result:
ok found '1.570796327', expected '1.570796327', error '0.000000000'
Test #17:
score: 0
Accepted
time: 0ms
memory: 7752kb
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.570796326794
result:
ok found '1.570796327', expected '1.570796327', error '0.000000000'
Test #18:
score: 0
Accepted
time: 1ms
memory: 9976kb
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.418644094132
result:
ok found '1.418644094', expected '1.418644094', error '0.000000000'
Test #19:
score: 0
Accepted
time: 0ms
memory: 7920kb
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.656117102219
result:
ok found '1.656117102', expected '1.656117102', error '0.000000000'
Test #20:
score: 0
Accepted
time: 2194ms
memory: 18816kb
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.567645716448
result:
ok found '1.567645716', expected '1.567645716', error '0.000000000'
Test #21:
score: 0
Accepted
time: 1730ms
memory: 17160kb
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.564802980856
result:
ok found '1.564802981', expected '1.564802981', error '0.000000000'
Test #22:
score: 0
Accepted
time: 2ms
memory: 9836kb
input:
4 -3 -4 -5 -4 2 -1 -3 -2
output:
0.472655643277
result:
ok found '0.472655643', expected '0.472655643', error '0.000000000'
Test #23:
score: 0
Accepted
time: 1ms
memory: 7880kb
input:
10 -3 -7 -5 9 -1 6 -8 2 -7 7 -7 9 4 -1 -5 8 -6 -3 5 1
output:
1.703347859091
result:
ok found '1.703347859', expected '1.703347859', error '0.000000000'
Test #24:
score: 0
Accepted
time: 1ms
memory: 5808kb
input:
3 -1000000000 0 1000000000 0 1000000000 1
output:
0.000000000499
result:
ok found '0.000000000', expected '0.000000000', error '0.000000000'
Test #25:
score: 0
Accepted
time: 1ms
memory: 7916kb
input:
3 -1000000000 0 1000000000 0 1000000000 3
output:
0.000000001499
result:
ok found '0.000000001', expected '0.000000001', error '0.000000000'
Test #26:
score: 0
Accepted
time: 1ms
memory: 9832kb
input:
3 -1000000000 0 1000000000 0 1000000000 2
output:
0.000000000999
result:
ok found '0.000000001', expected '0.000000001', error '0.000000000'
Test #27:
score: 0
Accepted
time: 0ms
memory: 9968kb
input:
3 -1000000000 0 1000000000 0 1000000000 5
output:
0.000000002499
result:
ok found '0.000000002', expected '0.000000002', error '0.000000000'
Test #28:
score: 0
Accepted
time: 2188ms
memory: 18648kb
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.570738488960
result:
ok found '1.570738489', expected '1.570738489', error '0.000000000'
Test #29:
score: 0
Accepted
time: 2172ms
memory: 18840kb
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.572402491884
result:
ok found '1.572402492', expected '1.572402492', error '0.000000000'
Test #30:
score: 0
Accepted
time: 2190ms
memory: 18976kb
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.567256817042
result:
ok found '1.567256817', expected '1.567256817', error '0.000000000'
Test #31:
score: 0
Accepted
time: 1096ms
memory: 19004kb
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.574006709558
result:
ok found '1.574006710', expected '1.574006710', error '0.000000000'
Test #32:
score: 0
Accepted
time: 1920ms
memory: 12716kb
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.000000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #33:
score: 0
Accepted
time: 1945ms
memory: 12612kb
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.000000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #34:
score: 0
Accepted
time: 2071ms
memory: 19028kb
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.677945044589
result:
ok found '2.677945045', expected '2.677945045', error '0.000000000'
Test #35:
score: 0
Accepted
time: 2036ms
memory: 18988kb
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.131789046110
result:
ok found '3.131789046', expected '3.131789046', error '0.000000000'
Test #36:
score: 0
Accepted
time: 2026ms
memory: 19012kb
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.140484006593
result:
ok found '3.140484007', expected '3.140484007', error '0.000000000'
Test #37:
score: 0
Accepted
time: 2180ms
memory: 12776kb
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.000000007305
result:
ok found '0.000000007', expected '0.000000007', error '0.000000000'
Test #38:
score: 0
Accepted
time: 2173ms
memory: 12576kb
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.000000007263
result:
ok found '0.000000007', expected '0.000000007', error '0.000000000'
Test #39:
score: 0
Accepted
time: 2140ms
memory: 18800kb
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.677945044589
result:
ok found '2.677945045', expected '2.677945045', error '0.000000000'
Test #40:
score: 0
Accepted
time: 2154ms
memory: 18772kb
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.131789046110
result:
ok found '3.131789046', expected '3.131789046', error '0.000000000'
Test #41:
score: 0
Accepted
time: 2137ms
memory: 18808kb
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.140484006593
result:
ok found '3.140484007', expected '3.140484007', error '0.000000000'
Test #42:
score: 0
Accepted
time: 2268ms
memory: 12764kb
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.566291852756
result:
ok found '1.566291853', expected '1.566291853', error '0.000000000'
Test #43:
score: 0
Accepted
time: 2287ms
memory: 12704kb
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.570796326794
result:
ok found '1.570796327', expected '1.570796327', error '0.000000000'
Test #44:
score: 0
Accepted
time: 2202ms
memory: 17240kb
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.570780621061
result:
ok found '1.570780621', expected '1.570780621', error '0.000000000'
Test #45:
score: 0
Accepted
time: 1124ms
memory: 17240kb
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.570796326794
result:
ok found '1.570796327', expected '1.570796327', error '0.000000000'
Test #46:
score: 0
Accepted
time: 1121ms
memory: 17356kb
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.570780617583
result:
ok found '1.570780618', expected '1.570780618', error '0.000000000'
Test #47:
score: 0
Accepted
time: 2219ms
memory: 17032kb
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.570780277387
result:
ok found '1.570780277', expected '1.570780277', error '0.000000000'
Test #48:
score: 0
Accepted
time: 2ms
memory: 5888kb
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.565420034509
result:
ok found '1.565420035', expected '1.565420035', error '0.000000000'
Test #49:
score: 0
Accepted
time: 571ms
memory: 14432kb
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.570780133249
result:
ok found '1.570780133', expected '1.570780133', error '0.000000000'