QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#189582 | #7229. Lines | haze | WA | 3ms | 4240kb | C++23 | 2.1kb | 2023-09-27 17:37:45 | 2023-09-27 17:37:46 |
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 work(ll g){
// cerr << g << endl;
double l = asin(-1), r = asin(1);
while(r - l > eps){
// cerr << l << ' ' << r << endl;
double mid = 0.50 * (l + r);
// cerr << "VALAS" << endl;
// irep(x,0,n-1)cerr << a[x][1] - a[x][0] * tan(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);
// if(abs(fx - fy) < eps){cerr << "M";return x > y;}
return fx < fy;});
ll cnt = 0;
// cerr << endl;
// cerr << tan(mid) << endl;
// irep(i,0,n-1)cerr << ord[i] << ' ';
// cerr << endl;
irep(i,0,n-1){
cnt += query(n - 1) - query(ord[i]);
add(ord[i]);
}
// cerr << endl;
clear();
if(cnt <= g)l = mid;
else r = mid;
}
// cerr << endl;
return l;
}
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: 4164kb
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: 3ms
memory: 4240kb
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: 0ms
memory: 4192kb
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: 3900kb
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: 1ms
memory: 4064kb
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: 1ms
memory: 4064kb
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: -100
Wrong Answer
time: 1ms
memory: 3904kb
input:
3 0 -1 3 -3 -4 1
output:
-0.463647609001
result:
wrong answer 1st numbers differ - expected: '2.6224465', found: '-0.4636476', error = '1.1767996'