QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#193129#7229. Linesjeffqi#RE 1842ms6408kbC++203.6kb2023-09-30 16:25:502023-09-30 16:25:50

Judging History

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

  • [2023-09-30 16:25:50]
  • 评测
  • 测评结果:RE
  • 用时:1842ms
  • 内存:6408kb
  • [2023-09-30 16:25:50]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(v) ((int)v.size())
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define ui unsigned int
#define ull unsigned ll
#define i128 __int128
using namespace std;

namespace qiqi {
	const double eps = 1e-10;
	int cmp(double x) {
		return x > eps ? 1 : x < -eps ? -1 : 0;
	}
	template<class T>
	struct Point {
		T x;
		T y;
		Point(T x_ = 0, T y_ = 0) : x(x_), y(y_) {}

		template<class U>
		operator Point<U>() {
			return Point<U>(U(x), U(y));
		}
		Point &operator+=(Point p) & {
			x += p.x;
			y += p.y;
			return *this;
		}
		Point &operator-=(Point p) & {
			x -= p.x;
			y -= p.y;
			return *this;
		}
		Point &operator*=(T v) & {
			x *= v;
			y *= v;
			return *this;
		}
		Point &operator/=(T v) & {
			x /= v;
			y /= v;
			return *this;
		}
		Point operator-() const {
			return Point(-x, -y);
		}
		friend Point operator+(Point a, Point b) {
			return a += b;
		}
		friend Point operator-(Point a, Point b) {
			return a -= b;
		}
		friend Point operator*(Point a, T b) {
			return a *= b;
		}
		friend Point operator/(Point a, T b) {
			return a /= b;
		}
		friend Point operator*(T a, Point b) {
			return b *= a;
		}
		friend bool operator==(Point a, Point b) {
			return a.x == b.x && a.y == b.y;
		}
		friend std::istream &operator>>(std::istream &is, Point &p) {
			return is >> p.x >> p.y;
		}
		friend std::ostream &operator<<(std::ostream &os, Point p) {
			return os << "(" << p.x << ", " << p.y << ")";
		}
	};

	template<class T>
	T dot(Point<T> a, Point<T> b) {
		return a.x * b.x + a.y * b.y;
	}

	template<class T>
	T cross(Point<T> a, Point<T> b) {
		return a.x * b.y - a.y * b.x;
	}

	struct BIT {
		int n; vi a;
		BIT(int n):n(n),a(n,0) {}
		int lbt(int x) {return x&(-x);}
		void upd(int x,int k) {
			for (int i = x+1; i <= n; i += lbt(i)) {
				a[i-1] += k;
			}
		}
		int qry(int x) {
			int k = 0;
			for (int i = x; i > 0; i -= lbt(i)) {
				k += a[i-1];
			}
			return k;
		}
	};

	using P = Point<double>;
	void main() {
		int n;
		cin >> n;
		vector<P> p(n);
		for (int i = 0; i < n; i++) {
			cin >> p[i];
		}
		auto calc = [&](double k) {
			ll res = 0;
			P q(cos(k),sin(k));
			vi o(n); iota(all(o),0);
			sort(all(o),[&](int a,int b) {
				return cmp(cross(q,p[b])-cross(q,p[a])) == 1;
			});
			vi rk(n);
			for (int i = 1; i < n; i++) {
				rk[o[i]] = rk[o[i-1]];
				if (cmp(cross(q,p[o[i]])-cross(q,p[o[i-1]])) == 1) {
					rk[o[i]]++;
				}
			}
			sort(all(o),[&](int a,int b) {
				return pair(p[a].y,-rk[a]) > pair(p[b].y,-rk[b]);
			});
			BIT bit(n);
			for (int i = 0; i < n; i++) {
				bit.upd(rk[o[i]],1);
				res += bit.qry(rk[o[i]]);
			}
			return res;
		};
		auto get = [&](ll k) {
			double l = 0,r = acos(-1);
			while (r-l > eps) {
				double mid = (l+r)/2;
				if (calc(mid) < k+1) {
					l = mid;
				}
				else {
					r = mid;
				}
			}
			return l;
		};
		ll m = 1ll*n*(n-1)/2;
		cout << (get(m/2)+get((m-1)/2))/2;
	}
}

int main() {
//	clock_t st = clock();
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cout << fixed << setprecision(15);

	int T = 1;
//	cin >> T;
	while (T--) {
		qiqi::main();
	}

//	cout << (double)(clock()-st)/CLOCKS_PER_SEC;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0 0
0 1
1 0

output:

1.570796326886329

result:

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

Test #2:

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

input:

4
0 0
0 1
1 0
1 1

output:

1.178097245141889

result:

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

Test #3:

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

input:

3
0 0
0 1000000000
1 0

output:

1.570796326794897

result:

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

Test #4:

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

input:

3
0 0
1 0
2 0

output:

0.000000000000000

result:

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

Test #5:

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

input:

3
5 -2
-5 -4
-4 4

output:

1.446441332235938

result:

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

Test #6:

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

input:

3
0 4
-3 -1
-4 4

output:

1.030376826530660

result:

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

Test #7:

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

input:

3
0 -1
3 -3
-4 1

output:

2.622446539287471

result:

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

Test #8:

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

input:

3
-5 -3
-3 0
3 5

output:

0.785398163397448

result:

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

Test #9:

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

input:

3
-5 3
-1 -2
5 -3

output:

2.601173153325557

result:

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

Test #10:

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

input:

3
-2 0
-3 3
1 -2

output:

2.245537268943483

result:

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

Test #11:

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

input:

3
-2 -1
-3 2
1 -3

output:

2.245537268943483

result:

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

Test #12:

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

input:

3
3 -3
1 -1
0 2

output:

2.111215827059133

result:

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

Test #13:

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

input:

3
0 -3
2 0
-3 0

output:

0.982793723223414

result:

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

Test #14:

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

input:

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

output:

1.802620131301159

result:

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

Test #15:

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

input:

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

output:

0.582952270233399

result:

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

Test #16:

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

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

result:

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

Test #17:

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

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

result:

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

Test #18:

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

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

result:

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

Test #19:

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

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

result:

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

Test #20:

score: 0
Accepted
time: 1805ms
memory: 6216kb

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

result:

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

Test #21:

score: 0
Accepted
time: 1421ms
memory: 5648kb

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

result:

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

Test #22:

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

input:

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

output:

0.472655643250451

result:

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

Test #23:

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

input:

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

output:

1.703347859069694

result:

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

Test #24:

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

input:

3
-1000000000 0
1000000000 0
1000000000 1

output:

0.000000000457162

result:

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

Test #25:

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

input:

3
-1000000000 0
1000000000 0
1000000000 3

output:

0.000000001462918

result:

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

Test #26:

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

input:

3
-1000000000 0
1000000000 0
1000000000 2

output:

0.000000000914324

result:

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

Test #27:

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

input:

3
-1000000000 0
1000000000 0
1000000000 5

output:

0.000000002468674

result:

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

Test #28:

score: 0
Accepted
time: 1818ms
memory: 6280kb

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

result:

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

Test #29:

score: 0
Accepted
time: 1842ms
memory: 6144kb

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

result:

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

Test #30:

score: 0
Accepted
time: 1841ms
memory: 6332kb

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

result:

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

Test #31:

score: 0
Accepted
time: 1827ms
memory: 6280kb

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

result:

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

Test #32:

score: 0
Accepted
time: 1132ms
memory: 6296kb

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

result:

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

Test #33:

score: 0
Accepted
time: 1132ms
memory: 6276kb

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

result:

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

Test #34:

score: 0
Accepted
time: 1116ms
memory: 6260kb

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

result:

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

Test #35:

score: 0
Accepted
time: 1106ms
memory: 6404kb

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

result:

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

Test #36:

score: 0
Accepted
time: 1101ms
memory: 6368kb

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

result:

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

Test #37:

score: 0
Accepted
time: 1673ms
memory: 6376kb

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

result:

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

Test #38:

score: 0
Accepted
time: 1667ms
memory: 6292kb

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

result:

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

Test #39:

score: 0
Accepted
time: 1424ms
memory: 6408kb

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

result:

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

Test #40:

score: 0
Accepted
time: 1452ms
memory: 6352kb

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

result:

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

Test #41:

score: 0
Accepted
time: 1449ms
memory: 6304kb

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

result:

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

Test #42:

score: 0
Accepted
time: 1771ms
memory: 6276kb

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

result:

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

Test #43:

score: 0
Accepted
time: 1768ms
memory: 6288kb

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

result:

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

Test #44:

score: -100
Runtime Error

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:


result: