QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#189624 | #7229. Lines | haze | TL | 551ms | 6004kb | C++23 | 1.9kb | 2023-09-27 18:40:30 | 2023-09-27 18:40:32 |
Judging History
answer
#include<bits/stdc++.h>
#define irep(i,l,r) for(int i = l; i <= r; ++i)
#define drep(i,r,l) for(int i = r; i >= l; --i)
#define ceil(pp,qq) (((pp)>0)^((qq)>0)?-Abs(pp)/Abs(qq):(pp)%(qq)?(pp)/(qq)+1:(pp)/(qq))
#define floor(pp,qq) (((pp)>0)^((qq)>0)?-ceil(abs(pp),abs(qq)):(pp)/(qq))
#define ll long long
using namespace std;
ll Abs(ll x){return x > 0 ? x : - x;}
inline ll read(){
char ch = getchar();
ll s = 0; bool w = 0;
while(!isdigit(ch)){if(ch == '-')w = 1;ch = getchar();}
while(isdigit(ch))s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
return w ? - s : s;
}
const int itinf = 2e9;
const ll llinf = 4e18;
const int mod = 1000000007;
const int N = 500009;
const double eps = 1e-11;
int n;
vector<array<double,2>>a;
vector<int>ord;
vector<int>t;
void add(int x){
++ x;
for(;x <= n; x += (x & -x))t[x] ++;
}
int query(int x){
++ x;
int ans = 0;
for(;x;x -= (x & -x))ans += t[x];
return ans;
}
void clear(){
irep(i,0,n)t[i] = 0;
}
ll calc(double mid){
sort(ord.begin(), ord.end(), [&mid](int x,int y){
double fx = a[x][1] - a[x][0] * tan(mid), fy = a[y][1] - a[y][0] * tan(mid);
return fx < fy;
}
);
ll cnt = 0;
irep(i,0,n-1){
cnt += i - query(ord[i]);
add(ord[i]);
}
clear();
return cnt;
}
double work(ll g){
//cerr << g << endl;
double l = asin(-1), r = asin(1);
while(r - l > eps){
double mid = 0.50 * (l + r);
ll cnt = calc(mid);
// cerr << tan(mid) << ' ' << cnt << endl;;
if(cnt < g)l = mid;
else r = mid;
}
return - l + asin(1);
}
int main(){
n = read();
ord.resize(n);
t.resize(n + 1);
irep(i,0,n-1){
int x = read(), y = - read();
a.push_back({1.0 * y,- 1.0 * x});
ord[i] = i;
}
sort(a.begin(), a.end());
ll sumn = 1ll * n * (n - 1) / 2;
printf("%0.12lf",sumn & 1 ? work((sumn >> 1ll) + 1) : 0.5 * (work(sumn >> 1ll) + work((sumn >> 1ll) + 1)));
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4000kb
input:
3 0 0 0 1 1 0
output:
1.570796326795
result:
ok found '1.570796327', expected '1.570796327', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3992kb
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: 4084kb
input:
3 0 0 0 1000000000 1 0
output:
1.570796326795
result:
ok found '1.570796327', expected '1.570796327', error '0.000000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3996kb
input:
3 0 0 1 0 2 0
output:
0.000000000006
result:
ok found '0.000000000', expected '0.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
3 5 -2 -5 -4 -4 4
output:
1.446441332253
result:
ok found '1.446441332', expected '1.446441332', error '0.000000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
3 0 4 -3 -1 -4 4
output:
1.030376826525
result:
ok found '1.030376827', expected '1.030376827', error '0.000000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4004kb
input:
3 0 -1 3 -3 -4 1
output:
2.622446539345
result:
ok found '2.622446539', expected '2.622446539', error '0.000000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 4000kb
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: 0ms
memory: 4064kb
input:
3 -5 3 -1 -2 5 -3
output:
2.601173153320
result:
ok found '2.601173153', expected '2.601173153', error '0.000000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 4000kb
input:
3 -2 0 -3 3 1 -2
output:
2.245537269023
result:
ok found '2.245537269', expected '2.245537269', error '0.000000000'
Test #11:
score: 0
Accepted
time: 1ms
memory: 4004kb
input:
3 -2 -1 -3 2 1 -3
output:
2.245537269023
result:
ok found '2.245537269', expected '2.245537269', error '0.000000000'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3904kb
input:
3 3 -3 1 -1 0 2
output:
2.111215827071
result:
ok found '2.111215827', expected '2.111215827', error '0.000000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 4000kb
input:
3 0 -3 2 0 -3 0
output:
0.982793723252
result:
ok found '0.982793723', expected '0.982793723', error '0.000000000'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3928kb
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: 1ms
memory: 3992kb
input:
5 -3 -2 2 -2 1 -2 1 -1 2 0
output:
0.582952270256
result:
ok found '0.582952270', expected '0.582952270', error '0.000000000'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3964kb
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.570796326795
result:
ok found '1.570796327', expected '1.570796327', error '0.000000000'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3960kb
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.570796326795
result:
ok found '1.570796327', expected '1.570796327', error '0.000000000'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3808kb
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.418644094135
result:
ok found '1.418644094', expected '1.418644094', error '0.000000000'
Test #19:
score: 0
Accepted
time: 1ms
memory: 4064kb
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.656117102222
result:
ok found '1.656117102', expected '1.656117102', error '0.000000000'
Test #20:
score: 0
Accepted
time: 550ms
memory: 6004kb
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.567645716451
result:
ok found '1.567645716', expected '1.567645716', error '0.000000000'
Test #21:
score: 0
Accepted
time: 430ms
memory: 5796kb
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.564802980859
result:
ok found '1.564802981', expected '1.564802981', error '0.000000000'
Test #22:
score: 0
Accepted
time: 0ms
memory: 4008kb
input:
4 -3 -4 -5 -4 2 -1 -3 -2
output:
0.472655643282
result:
ok found '0.472655643', expected '0.472655643', error '0.000000000'
Test #23:
score: 0
Accepted
time: 0ms
memory: 4008kb
input:
10 -3 -7 -5 9 -1 6 -8 2 -7 7 -7 9 4 -1 -5 8 -6 -3 5 1
output:
1.703347859093
result:
ok found '1.703347859', expected '1.703347859', error '0.000000000'
Test #24:
score: 0
Accepted
time: 2ms
memory: 4036kb
input:
3 -1000000000 0 1000000000 0 1000000000 1
output:
0.000000000503
result:
ok found '0.000000001', expected '0.000000000', error '0.000000000'
Test #25:
score: 0
Accepted
time: 2ms
memory: 4252kb
input:
3 -1000000000 0 1000000000 0 1000000000 3
output:
0.000000001503
result:
ok found '0.000000002', expected '0.000000001', error '0.000000000'
Test #26:
score: 0
Accepted
time: 2ms
memory: 4160kb
input:
3 -1000000000 0 1000000000 0 1000000000 2
output:
0.000000001000
result:
ok found '0.000000001', expected '0.000000001', error '0.000000000'
Test #27:
score: 0
Accepted
time: 2ms
memory: 4116kb
input:
3 -1000000000 0 1000000000 0 1000000000 5
output:
0.000000002503
result:
ok found '0.000000003', expected '0.000000002', error '0.000000000'
Test #28:
score: 0
Accepted
time: 541ms
memory: 5844kb
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.570738488963
result:
ok found '1.570738489', expected '1.570738489', error '0.000000000'
Test #29:
score: 0
Accepted
time: 551ms
memory: 5760kb
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.572402491887
result:
ok found '1.572402492', expected '1.572402492', error '0.000000000'
Test #30:
score: 0
Accepted
time: 545ms
memory: 5980kb
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.567256817043
result:
ok found '1.567256817', expected '1.567256817', error '0.000000000'
Test #31:
score: 0
Accepted
time: 281ms
memory: 5848kb
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.574006709560
result:
ok found '1.574006710', expected '1.574006710', error '0.000000000'
Test #32:
score: -100
Time Limit Exceeded
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...