QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#189599 | #7229. Lines | haze | WA | 2ms | 4252kb | C++23 | 1.9kb | 2023-09-27 18:00:56 | 2023-09-27 18:00:57 |
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;
}
double wk(ll g){
//cerr << g << endl;
double l = asin(-1), r = asin(1);
while(r - l > eps){
double mid = 0.50 * (l + r);
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();
// cerr << tan(mid) << ' ' << cnt << endl;
if(cnt <= g)l = mid;
else r = mid;
}
return l;
}
double work(ll g){
double s = wk(g);
if(s < 0)return wk(n - g) + asin(1) * 2;
return s;
}
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 * x,1.0 * y});
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: 2ms
memory: 4000kb
input:
3 0 0 0 1 1 0
output:
1.570796326789
result:
ok found '1.570796327', expected '1.570796327', error '0.000000000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 4252kb
input:
4 0 0 0 1 1 0 1 1
output:
1.178097245093
result:
ok found '1.178097245', expected '1.178097245', error '0.000000000'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3996kb
input:
3 0 0 0 1000000000 1 0
output:
1.570796326789
result:
ok found '1.570796327', expected '1.570796327', error '0.000000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3924kb
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: 0ms
memory: 4004kb
input:
3 5 -2 -5 -4 -4 4
output:
1.446441332247
result:
ok found '1.446441332', expected '1.446441332', error '0.000000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 4004kb
input:
3 0 4 -3 -1 -4 4
output:
1.030376826519
result:
ok found '1.030376827', expected '1.030376827', error '0.000000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
3 0 -1 3 -3 -4 1
output:
2.622446539339
result:
ok found '2.622446539', expected '2.622446539', error '0.000000000'
Test #8:
score: -100
Wrong Answer
time: 1ms
memory: 4008kb
input:
3 -5 -3 -3 0 3 5
output:
0.982793723246
result:
wrong answer 1st numbers differ - expected: '0.7853982', found: '0.9827937', error = '0.1973956'