QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#189582#7229. LineshazeWA 3ms4240kbC++232.1kb2023-09-27 17:37:452023-09-27 17:37:46

Judging History

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

  • [2023-09-27 17:37:46]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:4240kb
  • [2023-09-27 17:37:45]
  • 提交

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;
}

详细

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'