QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#179288#7229. LinesPhantomThreshold#AC ✓2287ms19028kbC++201.9kb2023-09-14 20:18:262023-09-14 20:18:27

Judging History

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

  • [2023-09-14 20:18:27]
  • 评测
  • 测评结果:AC
  • 用时:2287ms
  • 内存:19028kb
  • [2023-09-14 20:18:26]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define int long long
#define lowbit(x) ((x)&(-x))
using namespace std;

const int maxn = 105000;
const long double pi = acos(-1);
const long double eps = 1e-12;
//const long double inf = 2e9;

int n;
struct node
{
	int x,y;
	//friend long double operator *(const node &k1,const node &k2){ return k1.x*k2.x+k1.y*k2.y; }
}p[maxn];

pair<long double,int>a[maxn];
pair<long double,int>t[maxn];
int s[maxn];
void init()
{
	for(int i=1;i<=n;i++) s[i]=0;
}
void add(int x)
{
	for(;x<=n;x+=lowbit(x)) s[x]++;
}
int query(int x)
{
	int re=0;
	for(;x;x-=lowbit(x)) re+=s[x];
	return re;
}
int base;
int calc(long double mid)
{
	mid=mid-pi/2;
	long double k= tan(mid);
	
	for(int i=1;i<=n;i++)
	{
		a[i]=make_pair( p[i].x, 0 );
		t[i]=make_pair( p[i].y-k*p[i].x,i );
	}
	sort(t+1,t+n+1);
	
	for(int i=1;i<=n;i++) a[ t[i].second ].second=i;
	sort(a+1,a+n+1);
	
	init();
	int ret=0;
	for(int i=1;i<=n;)
	{
		int j=i;
		while(j<=n&&a[i].first==a[j].first)
		{
			ret+= (i-1)-query(a[j].second);
			j++;
		}
		while(i<j)
		{
			add(a[i].second);
			i++;
		}
	}
	return base+ret;
}
long double get_kth(int k)
{
	long double l=0,r= pi-eps;
	while(r-l>eps)
	{
		long double mid=(l+r)/2;
		int num= calc(mid);
		if(num>=k) r=mid;
		else l=mid;
	}
	return l;
}

signed main()
{
	ios_base::sync_with_stdio(false); ////////////////////////////////////////
	cin.tie(0);
	
	cin>>n;
	for(int i=1;i<=n;i++) 
	{
		cin>>p[i].x>>p[i].y;
		swap(p[i].x,p[i].y);
		p[i].y=-p[i].y;
	}
	
	base=0;
	map<int,int>mp;
	for(int i=1;i<=n;i++)
	{
		if(mp.count(p[i].x)>0) base+=mp[p[i].x];
		mp[p[i].x]++;
	}
	
	int N= n*(n-1)/2;
	long double ans;
	if(N%2==0) ans= ( get_kth(N/2)+get_kth(N/2+1) )/2;
	else ans= get_kth(N/2+1);
	
	cout<<fixed<<setprecision(12)<<ans<<endl;
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 9784kb

input:

3
0 0
0 1
1 0

output:

1.570796326794

result:

ok found '1.570796327', expected '1.570796327', error '0.000000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 7736kb

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

input:

3
0 0
0 1000000000
1 0

output:

1.570796326794

result:

ok found '1.570796327', expected '1.570796327', error '0.000000000'

Test #4:

score: 0
Accepted
time: 2ms
memory: 9788kb

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: 2ms
memory: 9824kb

input:

3
5 -2
-5 -4
-4 4

output:

1.446441332248

result:

ok found '1.446441332', expected '1.446441332', error '0.000000000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 7828kb

input:

3
0 4
-3 -1
-4 4

output:

1.030376826524

result:

ok found '1.030376827', expected '1.030376827', error '0.000000000'

Test #7:

score: 0
Accepted
time: 1ms
memory: 5696kb

input:

3
0 -1
3 -3
-4 1

output:

2.622446539343

result:

ok found '2.622446539', expected '2.622446539', error '0.000000000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 9796kb

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: 1ms
memory: 5708kb

input:

3
-5 3
-1 -2
5 -3

output:

2.601173153319

result:

ok found '2.601173153', expected '2.601173153', error '0.000000000'

Test #10:

score: 0
Accepted
time: 0ms
memory: 9784kb

input:

3
-2 0
-3 3
1 -2

output:

2.245537269018

result:

ok found '2.245537269', expected '2.245537269', error '0.000000000'

Test #11:

score: 0
Accepted
time: 2ms
memory: 9972kb

input:

3
-2 -1
-3 2
1 -3

output:

2.245537269018

result:

ok found '2.245537269', expected '2.245537269', error '0.000000000'

Test #12:

score: 0
Accepted
time: 2ms
memory: 9776kb

input:

3
3 -3
1 -1
0 2

output:

2.111215827065

result:

ok found '2.111215827', expected '2.111215827', error '0.000000000'

Test #13:

score: 0
Accepted
time: 2ms
memory: 9788kb

input:

3
0 -3
2 0
-3 0

output:

0.982793723247

result:

ok found '0.982793723', expected '0.982793723', error '0.000000000'

Test #14:

score: 0
Accepted
time: 0ms
memory: 9732kb

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

input:

5
-3 -2
2 -2
1 -2
1 -1
2 0

output:

0.582952270255

result:

ok found '0.582952270', expected '0.582952270', error '0.000000000'

Test #16:

score: 0
Accepted
time: 2ms
memory: 9868kb

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

result:

ok found '1.570796327', expected '1.570796327', error '0.000000000'

Test #17:

score: 0
Accepted
time: 0ms
memory: 7752kb

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

result:

ok found '1.570796327', expected '1.570796327', error '0.000000000'

Test #18:

score: 0
Accepted
time: 1ms
memory: 9976kb

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

result:

ok found '1.418644094', expected '1.418644094', error '0.000000000'

Test #19:

score: 0
Accepted
time: 0ms
memory: 7920kb

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

result:

ok found '1.656117102', expected '1.656117102', error '0.000000000'

Test #20:

score: 0
Accepted
time: 2194ms
memory: 18816kb

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

result:

ok found '1.567645716', expected '1.567645716', error '0.000000000'

Test #21:

score: 0
Accepted
time: 1730ms
memory: 17160kb

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

result:

ok found '1.564802981', expected '1.564802981', error '0.000000000'

Test #22:

score: 0
Accepted
time: 2ms
memory: 9836kb

input:

4
-3 -4
-5 -4
2 -1
-3 -2

output:

0.472655643277

result:

ok found '0.472655643', expected '0.472655643', error '0.000000000'

Test #23:

score: 0
Accepted
time: 1ms
memory: 7880kb

input:

10
-3 -7
-5 9
-1 6
-8 2
-7 7
-7 9
4 -1
-5 8
-6 -3
5 1

output:

1.703347859091

result:

ok found '1.703347859', expected '1.703347859', error '0.000000000'

Test #24:

score: 0
Accepted
time: 1ms
memory: 5808kb

input:

3
-1000000000 0
1000000000 0
1000000000 1

output:

0.000000000499

result:

ok found '0.000000000', expected '0.000000000', error '0.000000000'

Test #25:

score: 0
Accepted
time: 1ms
memory: 7916kb

input:

3
-1000000000 0
1000000000 0
1000000000 3

output:

0.000000001499

result:

ok found '0.000000001', expected '0.000000001', error '0.000000000'

Test #26:

score: 0
Accepted
time: 1ms
memory: 9832kb

input:

3
-1000000000 0
1000000000 0
1000000000 2

output:

0.000000000999

result:

ok found '0.000000001', expected '0.000000001', error '0.000000000'

Test #27:

score: 0
Accepted
time: 0ms
memory: 9968kb

input:

3
-1000000000 0
1000000000 0
1000000000 5

output:

0.000000002499

result:

ok found '0.000000002', expected '0.000000002', error '0.000000000'

Test #28:

score: 0
Accepted
time: 2188ms
memory: 18648kb

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

result:

ok found '1.570738489', expected '1.570738489', error '0.000000000'

Test #29:

score: 0
Accepted
time: 2172ms
memory: 18840kb

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

result:

ok found '1.572402492', expected '1.572402492', error '0.000000000'

Test #30:

score: 0
Accepted
time: 2190ms
memory: 18976kb

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

result:

ok found '1.567256817', expected '1.567256817', error '0.000000000'

Test #31:

score: 0
Accepted
time: 1096ms
memory: 19004kb

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

result:

ok found '1.574006710', expected '1.574006710', error '0.000000000'

Test #32:

score: 0
Accepted
time: 1920ms
memory: 12716kb

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:

0.000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #33:

score: 0
Accepted
time: 1945ms
memory: 12612kb

input:

100000
57050460 0
-375026139 0
-820386623 0
-99980585 0
-512640358 0
167544347 0
-232780265 0
-373340677 0
58293973 0
-784457940 0
383364961 0
487333353 0
609709989 0
666053328 0
-383548055 0
910405928 0
149861137 0
-254137401 0
-577038938 0
-84360914 0
573266580 0
859984770 0
-71001073 0
867939952 ...

output:

0.000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #34:

score: 0
Accepted
time: 2071ms
memory: 19028kb

input:

100000
876809794 -438404747
394286770 -197143235
-367448514 183724407
-383434666 191717483
936480596 -468240148
-40502056 20251178
725524068 -362761884
181615020 -90807360
-477458542 238729421
922627006 -461313353
-106096964 53048632
431977902 -215988801
-164082662 82041481
-686224656 343112478
-915...

output:

2.677945044589

result:

ok found '2.677945045', expected '2.677945045', error '0.000000000'

Test #35:

score: 0
Accepted
time: 2036ms
memory: 18988kb

input:

100000
-154037240 1510270
362293900 -3551800
2089162 -20381
-717258188 7032044
-424230650 4159225
-556396946 5454973
-886314620 8689460
-265795274 2605937
-930613526 9123763
-594000164 5823632
927217330 -9090265
-325966706 3195853
368042926 -3608163
675258664 -6620082
-772772504 7576302
392022922 -3...

output:

3.131789046110

result:

ok found '3.131789046', expected '3.131789046', error '0.000000000'

Test #36:

score: 0
Accepted
time: 2026ms
memory: 19012kb

input:

100000
412444110 -457155
-684758612 759256
479239014 -531207
390243184 -432542
453834184 -503042
-680452464 754482
866004888 -959994
483779682 -536241
-149556912 165906
937503722 -1039261
334160432 -370366
-855163550 948175
-900129152 998026
-638461658 707929
90074722 -99761
-264980440 293870
-59571...

output:

3.140484006593

result:

ok found '3.140484007', expected '3.140484007', error '0.000000000'

Test #37:

score: 0
Accepted
time: 2180ms
memory: 12776kb

input:

100000
796270214 1
-951846498 0
217668093 -2
-154910102 0
546144954 2
-886725978 -1
607295668 -1
81163900 0
842244991 0
394451733 2
-202184886 0
-296096210 0
550660940 -1
-177897556 1
-114486127 0
-419083768 1
843168056 1
-889488949 -2
-276903726 0
-682069189 -2
629500056 0
-207727363 2
-580841513 -...

output:

0.000000007305

result:

ok found '0.000000007', expected '0.000000007', error '0.000000000'

Test #38:

score: 0
Accepted
time: 2173ms
memory: 12576kb

input:

100000
-253706492 2
-226875621 2
362330838 2
-795605493 2
-215290842 -2
707063086 0
-873673230 -2
-481532653 -1
-830595165 1
748511407 0
809118374 2
1935598 0
-466786749 2
280720810 0
-568005292 2
42343361 2
-484237657 0
-411967860 -2
-364775056 -2
918375933 0
-627927595 -1
-914082092 -1
-236146640 ...

output:

0.000000007263

result:

ok found '0.000000007', expected '0.000000007', error '0.000000000'

Test #39:

score: 0
Accepted
time: 2140ms
memory: 18800kb

input:

100000
934702833 -467351271
-131493362 65746831
913964656 -456982181
627793697 -313896700
-638371333 319185816
976407872 -488203783
-968962292 484481297
565975688 -282987694
-202963342 101481827
-811264552 405632422
-768479282 384239788
115616122 -57807913
-583740418 291870360
-291751130 145875716
1...

output:

2.677945044589

result:

ok found '2.677945045', expected '2.677945045', error '0.000000000'

Test #40:

score: 0
Accepted
time: 2154ms
memory: 18772kb

input:

100000
-668200264 6551087
86496002 -847902
-871928849 8548421
-136205907 1335452
-402219969 3943437
-259323369 2542482
-467469268 4583131
-840900142 8244217
204026622 -2000159
724703160 -7104827
-851573316 8348862
-53404139 523674
-624909125 6126662
-823741703 8076002
-738369842 7239018
101639630 -9...

output:

3.131789046110

result:

ok found '3.131789046', expected '3.131789046', error '0.000000000'

Test #41:

score: 0
Accepted
time: 2137ms
memory: 18808kb

input:

100000
595966829 -660620
-51714261 57430
991615602 -1099248
-863804708 957752
902860607 -1000854
772085940 -855873
-55307834 61418
870845924 -965357
-466679365 517486
638883092 -708194
512483125 -568062
-375955304 416905
273537917 -303162
685640068 -760038
-59830465 66428
248798757 -275725
-65529026...

output:

3.140484006593

result:

ok found '3.140484007', expected '3.140484007', error '0.000000000'

Test #42:

score: 0
Accepted
time: 2268ms
memory: 12764kb

input:

100000
140 20
2 -114
152 -60
-82 123
-78 -42
-64 173
155 -18
-159 -124
88 6
76 -80
-111 -123
-49 150
155 -125
-107 161
-66 -133
67 -49
-17 -143
32 91
87 -104
-132 -170
84 65
87 -164
114 -56
24 -40
59 -34
24 -22
38 -57
-169 10
139 132
44 11
66 -100
-85 176
13 -173
-88 111
-45 -95
9 173
-141 74
-71 15...

output:

1.566291852756

result:

ok found '1.566291853', expected '1.566291853', error '0.000000000'

Test #43:

score: 0
Accepted
time: 2287ms
memory: 12704kb

input:

100000
-79 -25
-117 178
-70 221
-291 71
137 117
-234 -236
138 -47
-242 -167
-126 26
-39 49
240 -99
215 -174
106 -46
201 -180
172 -177
121 205
172 -115
63 25
-194 168
-295 -230
40 -91
190 230
25 -290
-124 114
176 271
-60 160
26 134
254 -57
-256 -4
153 -254
244 107
248 118
280 205
-148 115
-226 78
64 ...

output:

1.570796326794

result:

ok found '1.570796327', expected '1.570796327', error '0.000000000'

Test #44:

score: 0
Accepted
time: 2202ms
memory: 17240kb

input:

100000
74068734 -67184987
-73589858 -67709177
-63969660 -76862751
-90718064 42074133
-85849482 51282222
99386751 -11057737
99242656 -12283938
44456013 89574900
-42225124 -90647883
-85086246 52538849
-39587889 91830272
-88887165 45815628
82700993 -56218730
-91952953 39302090
6987486 99755576
99035725...

output:

1.570780621061

result:

ok found '1.570780621', expected '1.570780621', error '0.000000000'

Test #45:

score: 0
Accepted
time: 1124ms
memory: 17240kb

input:

99999
400813117 -805821844
874374859 -213233688
33553856 899374304
853659607 285070648
884703587 -165225789
757339336 -486248012
-522420355 -732855355
765731649 472921813
-864587019 -249978569
-759849679 482315731
-815400632 -380948563
-805758874 -400939690
-588492236 680938240
-553669423 -709542225...

output:

1.570796326794

result:

ok found '1.570796327', expected '1.570796327', error '0.000000000'

Test #46:

score: 0
Accepted
time: 1121ms
memory: 17356kb

input:

99999
99957306 -2955708
-9788208 99519803
-31843316 -94794095
-62763244 -77850073
80074973 -59901141
-84942988 -52768440
-41307853 -91068987
-31530448 -94898623
327725 99999566
41438558 91010697
73435383 -67877667
96362459 26729655
98488617 -17325871
-99719603 7470125
-17485840 -98459081
21842916 97...

output:

1.570780617583

result:

ok found '1.570780618', expected '1.570780618', error '0.000000000'

Test #47:

score: 0
Accepted
time: 2219ms
memory: 17032kb

input:

100000
-94881770 31583126
44754159 -89425361
87229737 -48896753
77708105 62941177
90472101 42601668
-91109174 -41219142
-53431299 -84527608
98536311 -17046435
-54051247 84134535
99973514 2306724
-54541944 83817259
-40120830 91599640
99916841 4080796
8127849 -99668151
91015903 -41425121
91544457 4024...

output:

1.570780277387

result:

ok found '1.570780277', expected '1.570780277', error '0.000000000'

Test #48:

score: 0
Accepted
time: 2ms
memory: 5888kb

input:

201
-100 10000
-99 9801
-98 9604
-97 9409
-96 9216
-95 9025
-94 8836
-93 8649
-92 8464
-91 8281
-90 8100
-89 7921
-88 7744
-87 7569
-86 7396
-85 7225
-84 7056
-83 6889
-82 6724
-81 6561
-80 6400
-79 6241
-78 6084
-77 5929
-76 5776
-75 5625
-74 5476
-73 5329
-72 5184
-71 5041
-70 4900
-69 4761
-68 46...

output:

1.565420034509

result:

ok found '1.565420035', expected '1.565420035', error '0.000000000'

Test #49:

score: 0
Accepted
time: 571ms
memory: 14432kb

input:

62003
-31001 961062001
-31000 961000000
-30999 960938001
-30998 960876004
-30997 960814009
-30996 960752016
-30995 960690025
-30994 960628036
-30993 960566049
-30992 960504064
-30991 960442081
-30990 960380100
-30989 960318121
-30988 960256144
-30987 960194169
-30986 960132196
-30985 960070225
-3098...

output:

1.570780133249

result:

ok found '1.570780133', expected '1.570780133', error '0.000000000'