QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#189624#7229. LineshazeTL 551ms6004kbC++231.9kb2023-09-27 18:40:302023-09-27 18:40:32

Judging History

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

  • [2023-09-27 18:40:32]
  • 评测
  • 测评结果:TL
  • 用时:551ms
  • 内存:6004kb
  • [2023-09-27 18:40:30]
  • 提交

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...

output:


result: