QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#189584#7229. LineshazeWA 2ms4252kbC++231.8kb2023-09-27 17:39:112023-09-27 17:39:11

Judging History

你现在查看的是最新测评结果

  • [2023-09-27 17:39:11]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4252kb
  • [2023-09-27 17:39:11]
  • 提交

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){
	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();
		if(cnt <= g)l = mid;
		else r = mid;
	}
	return l < 0 ? l + asin(1) : 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: 4252kb

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: 0ms
memory: 4244kb

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: 4244kb

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: 3928kb

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: 4112kb

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: 3868kb

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: 0ms
memory: 3812kb

input:

3
0 -1
3 -3
-4 1

output:

1.107148717794

result:

wrong answer 1st numbers differ - expected: '2.6224465', found: '1.1071487', error = '0.5778184'