QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#478837#1196. Fun Regioncrimson231AC ✓18ms4080kbC++179.4kb2024-07-15 11:41:572024-07-15 11:41:57

Judging History

This is the latest submission verdict.

  • [2024-07-15 11:41:57]
  • Judged
  • Verdict: AC
  • Time: 18ms
  • Memory: 4080kb
  • [2024-07-15 11:41:57]
  • Submitted

answer

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <vector>
#include <deque>
typedef long long ll;
//typedef long double ld;
typedef double ld;
const ld INF = 1e17;
const ld TOL = 1e-10;
const ld PI = acos(-1);
const int LEN = 2e3 + 5;
int N, M, T, Q;
bool V[LEN];
bool zero(const ld& x) { return std::abs(x) < TOL; }
int sign(const ld& x) { return x < -TOL ? -1 : x > TOL; }

struct Pos {
	ld x, y;
	Pos(ld X = 0, ld Y = 0) : x(X), y(Y) {}
	bool operator == (const Pos& p) const { return zero(x - p.x) && zero(y - p.y); }
	bool operator != (const Pos& p) const { return !zero(x - p.x) || !zero(y - p.y); }
	bool operator < (const Pos& p) const { return zero(x - p.x) ? y < p.y : x < p.x; }
	Pos operator + (const Pos& p) const { return { x + p.x, y + p.y }; }
	Pos operator - (const Pos& p) const { return { x - p.x, y - p.y }; }
	Pos operator * (const ld& scalar) const { return { x * scalar, y * scalar }; }
	Pos operator / (const ld& scalar) const { return { x / scalar, y / scalar }; }
	ld operator * (const Pos& p) const { return { x * p.x + y * p.y }; }
	ld operator / (const Pos& p) const { return { x * p.y - y * p.x }; }
	Pos operator - () const { return { -x, -y }; }
	Pos operator ~ () const { return { -y, x }; }
	Pos operator ! () const { return { y, x }; }
	ld Euc() const { return x * x + y * y; }
	ld mag() const { return sqrt(Euc()); }
	Pos unit() const { return *this / mag(); }
	ld rad() const { return atan2(y, x); }
	friend ld rad(const Pos& p1, const Pos& p2) { return atan2l(p1 / p2, p1 * p2); }
	int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0); }
	friend bool cmpq(const Pos& a, const Pos& b) { return (a.quad() != b.quad()) ? a.quad() < b.quad() : a / b > 0; }
	friend std::istream& operator >> (std::istream& is, Pos& p) { is >> p.x >> p.y; return is; }
	friend std::ostream& operator << (std::ostream& os, const Pos& p) { os << p.x << " " << p.y; return os; }
}; const Pos O = { 0, 0 };
typedef std::vector<Pos> Polygonf;
struct Linear {//ps[0] -> ps[1] :: refer to bulijiojiodibuliduo
	Pos ps[2];
	Pos dir_;
	Pos& operator[](int i) { return ps[i]; }
	Pos dir() const { return dir_; }
	Linear(Pos a = Pos(0, 0), Pos b = Pos(0, 0)) {
		ps[0] = a;
		ps[1] = b;
		dir_ = (ps[1] - ps[0]).unit();
	}
	bool include(const Pos& p) const { return sign(dir_ / (p - ps[0])) > 0; }
	Linear push() const {//push eps outward
		const double eps = 1e-8;
		Pos delta = ~(ps[1] - ps[0]).unit() * eps;
		return Linear(ps[0] + delta, ps[1] + delta);
	}
	Linear operator + (const double eps) const {//push eps outward
		Pos delta = ~(ps[1] - ps[0]).unit() * eps;
		return Linear(ps[0] + delta, ps[1] + delta);
	}
	Linear operator - (const double eps) const {//pull eps inward
		Pos delta = ~(ps[1] - ps[0]).unit() * eps;
		return Linear(ps[0] - delta, ps[1] - delta);
	}
	friend bool parallel(const Linear& l0, const Linear& l1) { return zero(l0.dir() / l1.dir()); }
	friend bool same_dir(const Linear& l0, const Linear& l1) { return parallel(l0, l1) && l0.dir() * l1.dir() > 0; }
	bool operator < (const Linear& l0) const {
		if (same_dir(*this, l0)) return l0.include(ps[0]);
		else return cmpq(this->dir(), l0.dir());
	}
	bool operator == (const Linear& l0) const {
		return ps[0] == l0.ps[0] && ps[1] == l0.ps[1] && dir_ == l0.dir_;
	}
};
typedef std::vector<Linear> VHP;
ld cross(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) / (d3 - d2); }
int ccw(const Pos& d1, const Pos& d2, const Pos& d3) { ld ret = cross(d1, d2, d3); return sign(ret); }
Pos intersection(const Pos& p1, const Pos& p2, const Pos& q1, const Pos& q2) { ld a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2); return (p1 * a2 + p2 * a1) / (a1 + a2); }
Pos intersection(Linear& l1, Linear& l2) { return intersection(l1[0], l1[1], l2[0], l2[1]); }
std::vector<Pos> half_plane_intersection(std::vector<Linear>& HP) {//refer to bulijiojiodibuliduo
	auto check = [&](Linear& u, Linear& v, Linear& w) -> bool {
		return w.include(intersection(u, v));
		};
	std::sort(HP.begin(), HP.end());
	HP.erase(unique(HP.begin(), HP.end()), HP.end());
	std::deque<Linear> dq;
	int sz = HP.size();
	for (int i = 0; i < sz; ++i) {
		if (i && same_dir(HP[i], HP[(i - 1) % sz])) continue;
		while (dq.size() > 1 && !check(dq[dq.size() - 2], dq[dq.size() - 1], HP[i])) dq.pop_back();
		while (dq.size() > 1 && !check(dq[1], dq[0], HP[i])) dq.pop_front();
		dq.push_back(HP[i]);
	}
	while (dq.size() > 2 && !check(dq[dq.size() - 2], dq[dq.size() - 1], dq[0])) dq.pop_back();
	while (dq.size() > 2 && !check(dq[1], dq[0], dq[dq.size() - 1])) dq.pop_front();
	sz = dq.size();
	if (sz < 3) return {};
	std::vector<Pos> HPI;
	for (int i = 0; i < sz; ++i) HPI.push_back(intersection(dq[i], dq[(i + 1) % sz]));
	return HPI;
}
ld area(const Polygonf& H) {
	Pos pivot = Pos(0, 0);
	ld ret = 0;
	int h = H.size();
	for (int i = 0; i < h; i++) {
		const Pos& cur = H[i], & nxt = H[(i + 1) % h];
		ret += cross(pivot, cur, nxt);
	}
	return ret * .5;
}
struct Pii {
	int x, y;
	int i;
	Pii(int X = 0, int Y = 0) : x(X), y(Y) { i = -1; }
	bool operator == (const Pii& p) const { return x == p.x && y == p.y; }
	bool operator != (const Pii& p) const { return x != p.x || y != p.y; }
	bool operator < (const Pii& p) const { return x == p.x ? y < p.y : x < p.x; }
	Pii operator + (const Pii& p) const { return { x + p.x, y + p.y }; }
	Pii operator - (const Pii& p) const { return { x - p.x, y - p.y }; }
	Pii operator * (const int& n) const { return { x * n, y * n }; }
	Pii operator / (const int& n) const { return { x / n, y / n }; }
	ll operator * (const Pii& p) const { return { (ll)x * p.x + (ll)y * p.y }; }
	ll operator / (const Pii& p) const { return { (ll)x * p.y - (ll)y * p.x }; }
	friend std::istream& operator >> (std::istream& is, Pii& p) { is >> p.x >> p.y; return is; }
	friend std::ostream& operator << (std::ostream& os, const Pii& p) { os << p.x << " " << p.y; return os; }
};
typedef std::vector<Pii> Polygon;
ll cross(const Pii& d1, const Pii& d2, const Pii& d3) { return (d2 - d1) / (d3 - d2); }
ll dot(const Pii& d1, const Pii& d2, const Pii& d3) { return (d2 - d1) * (d3 - d2); }
int ccw(const Pii& d1, const Pii& d2, const Pii& d3) { ll ret = cross(d1, d2, d3); return ret < 0 ? -1 : !!ret; }
bool on_seg_strong(const Pii& d1, const Pii& d2, const Pii& d3) { ll ret = dot(d1, d3, d2); return !ccw(d1, d2, d3) && ret >= 0; }
bool inner_check(Pii d1, Pii d2, Pii d3, const Pii& t) {
	if (ccw(d1, d2, d3) < 0) std::swap(d2, d3);
	return ccw(d1, d2, t) > 0 && ccw(d2, d3, t) > 0 && ccw(d3, d1, t) > 0;
}
ll area(const Polygon& H) {
	Pii pivot = Pii(0, 0);
	ld ret = 0;
	int h = H.size();
	for (int i = 0; i < h; i++) {
		const Pii& cur = H[i], & nxt = H[(i + 1) % h];
		ret += cross(pivot, cur, nxt);
	}
	return ret;
}
void norm(Polygon& H, const bool& f = 1) {
	if (f && area(H) < 0) std::reverse(H.begin(), H.end());//ccw
	if (!f && area(H) > 0) std::reverse(H.begin(), H.end());//cw
	return;
}
Pos P(const Pii& p) { return Pos(p.x, p.y); }
Pii P(const Pos& p) { return Pii(p.x, p.y); }
void solve() {
	std::cin.tie(0)->sync_with_stdio(0);
	std::cout.tie(0);
	std::cout << std::fixed;
	std::cout.precision(15);
	std::cin >> N;
	Polygon H(N);
	for (Pii& p : H) std::cin >> p;
	norm(H, 0);//cw

	//convex
	bool f = 1;
	for (int i = 0; i < N; i++) {
		Pii& pre = H[(i - 1 + N) % N], & cur = H[i], & nxt = H[(i + 1) % N];
		int CCW = ccw(pre, cur, nxt);
		assert(CCW);
		if (CCW > 0) { f = 0; }
	}
	if (f) { std::cout << std::abs(area(H)) * .5 << "\n"; return; }
	//convex

	//concave
	for (int i = 0; i < N; i++) {
		Pii& pre = H[(i - 1 + N) % N], & cur = H[i], & nxt = H[(i + 1) % N];
		if (ccw(pre, cur, nxt) > 0) {
			Pii& nnxt = H[(i + 2) % N];
			if (ccw(cur, nxt, nnxt) > 0) continue;
			int j;
			for (j = (i + 2) % N; j != (i - 1 + N) % N; j = (j + 1) % N) {
				int j2 = (j + 1) % N;
				if (!ccw(cur, nxt, H[j2]) ||
					(ccw(cur, nxt, H[j]) != ccw(cur, nxt, H[j2]))) {
					break;
				}
			}
			cur.i = (j + 1) % N;
			for (int k = (i + 2) % N; k != (j + 1) % N; k = (k + 1) % N) {
				int j2 = (k + 1) % N;
				if (ccw(cur, nxt, H[k]) > 0 ||
					on_seg_strong(cur, H[k], nxt) ||
					inner_check(cur, H[k], H[j2], nxt)) {
					cur.i = -1;
					break;
				}
			}
		}
		else continue;
	}
	VHP vhp;
	for (int i = 0; i < N; i++) {
		if (H[i].i == -1) continue;
		Pii& cur = H[i], & nxt = H[(i + 1) % N];
		vhp.push_back(Linear(P(nxt), P(cur)));
		int j, k = -1;
		for (j = (i + 2) % N; j != cur.i; j = (j + 1) % N) {
			if (H[j].i != -1) {
				k = j;
				break;
			}
		}
		if (k == -1) {
			for (j = (i + 1) % N; j != cur.i; j = (j + 1) % N) {
				int j2 = (j + 1) % N;
				vhp.push_back(Linear(P(H[j2]), P(H[j])));
			}
		}
		else {
			int k1 = (k + 1) % N;
			for (j = (i + 1) % N; j != k; j = (j + 1) % N) {
				assert(H[j].i == -1);
				int j2 = (j + 1) % N;
				int ccw1 = ccw(H[k], H[k1], H[j]);
				int ccw2 = ccw(H[k], H[k1], H[j2]);
				if (ccw1 == -1 && ccw2 == -1) {
					vhp.push_back(Linear(P(H[j2]), P(H[j])));
				}
				else if ((ccw1 == -1 || ccw2 == -1) && inner_check(H[k1], H[j], H[j2], H[k])) {
					vhp.push_back(Linear(P(H[j2]), P(H[j])));
					break;
				}
			}
		}
	}
	Polygonf hpi = half_plane_intersection(vhp);
	std::cout << area(hpi) << "\n";
	return;
}
int main() { solve(); return 0; }//boj18219 ICPC 2019 Asia Yokohama Regional J Fun Region


详细

Test #1:

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

input:

4
10 0
20 10
10 30
0 10

output:

300.000000000000000

result:

ok found '300.0000000', expected '300.0000000', error '0.0000000'

Test #2:

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

input:

10
145 269
299 271
343 193
183 139
408 181
356 324
176 327
147 404
334 434
102 424

output:

12658.313019131075635

result:

ok found '12658.3130191', expected '12658.3130191', error '0.0000000'

Test #3:

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

input:

6
144 401
297 322
114 282
372 178
197 271
368 305

output:

0.000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #4:

score: 0
Accepted
time: 12ms
memory: 3892kb

input:

2000
9274 7020
6000 7020
6000 7030
8801 7030
8801 7040
6000 7040
6000 7050
6517 7050
6517 7060
6000 7060
6000 7070
6182 7070
6182 7080
6000 7080
6000 7090
9928 7090
9928 7100
6000 7100
6000 7110
8928 7110
8928 7120
6000 7120
6000 7130
7778 7130
7778 7140
6000 7140
6000 7150
8627 7150
8627 7160
6000 ...

output:

80000.000000000000000

result:

ok found '80000.0000000', expected '80000.0000000', error '0.0000000'

Test #5:

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

input:

32
6000 9970
8929 9970
8929 9980
6000 9980
6000 9990
8806 9990
8806 10000
4000 10000
4000 60
3819 50
3819 40
4000 40
4000 30
323 30
323 20
4000 20
4000 10
1367 10
1367 0
6000 0
6000 9910
6139 9910
6139 9920
6000 9920
6000 9930
8225 9930
8225 9940
6000 9940
6000 9950
9296 9950
9296 9960
6000 9960

output:

19760000.000000000000000

result:

ok found '19760000.0000000', expected '19760000.0000000', error '0.0000000'

Test #6:

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

input:

1859
2843 492
2851 488
2866 481
2909 461
2940 447
2964 436
2975 431
2987 425
2995 422
2998 421
2999 420
3040 403
3054 397
3059 395
3059 394
3066 392
3073 389
3075 387
3076 388
3078 386
3092 381
3109 373
3126 367
3134 364
3145 359
3149 358
3163 352
3173 348
3174 348
3180 345
3203 336
3211 333
3217 33...

output:

2079546.000000000000000

result:

ok found '2079546.0000000', expected '2079546.0000000', error '0.0000000'

Test #7:

score: 0
Accepted
time: 18ms
memory: 3896kb

input:

1844
9223 2327
9225 2330
9231 2340
9233 2343
9234 2344
9238 2350
9263 2392
9264 2393
9268 2399
9279 2417
9280 2419
9298 2451
9302 2457
9305 2461
9327 2498
9357 2552
9365 2566
9367 2568
9368 2571
9379 2591
9386 2603
9398 2626
9408 2644
9413 2655
9418 2663
9431 2689
9436 2698
9451 2728
9462 2749
9469 ...

output:

1418060.000000000000000

result:

ok found '1418060.0000000', expected '1418060.0000000', error '0.0000000'

Test #8:

score: 0
Accepted
time: 18ms
memory: 3896kb

input:

1861
5509 29
5515 29
5550 33
5559 33
5578 36
5601 38
5612 40
5676 48
5686 49
5687 50
5689 50
5696 51
5699 52
5709 52
5722 55
5724 55
5745 58
5761 60
5763 60
5791 65
5798 66
5814 69
5819 69
5903 84
5913 86
5916 87
5941 92
5965 97
5974 98
5979 99
5986 100
5995 102
6038 111
6048 113
6050 114
6051 114
6...

output:

1027161.000000000000000

result:

ok found '1027161.0000000', expected '1027161.0000000', error '0.0000000'

Test #9:

score: 0
Accepted
time: 18ms
memory: 3988kb

input:

1835
680 7513
663 7483
654 7468
651 7461
648 7457
643 7448
630 7425
614 7395
602 7373
600 7371
596 7363
577 7328
570 7313
560 7295
544 7262
539 7253
536 7248
517 7208
516 7206
512 7199
510 7195
499 7172
480 7132
468 7108
453 7075
453 7074
438 7039
437 7039
433 7031
415 6988
412 6984
409 6975
408 697...

output:

13822236.000000000000000

result:

ok found '13822236.0000000', expected '13822236.0000000', error '0.0000000'

Test #10:

score: 0
Accepted
time: 18ms
memory: 3896kb

input:

1858
9984 5375
9983 5383
9981 5413
9981 5418
9979 5441
9978 5446
9977 5459
9974 5485
9972 5503
9972 5514
9971 5514
9969 5535
9969 5536
9965 5570
9964 5585
9955 5656
9952 5678
9950 5691
9948 5701
9946 5720
9945 5723
9945 5725
9944 5731
9941 5757
9939 5767
9935 5790
9935 5791
9930 5820
9929 5830
9927 ...

output:

2490324.500000000000000

result:

ok found '2490324.5000000', expected '2490324.5000000', error '0.0000000'

Test #11:

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

input:

20
2340 769
3619 197
3795 149
5653 45
6914 383
7134 480
8823 1781
8989 1989
9211 2308
9332 2507
9781 3542
9828 3709
9859 3830
9925 4147
9916 5905
772 2336
1565 1370
1853 1118
1864 1109
2045 969

output:

29346414.000000000000000

result:

ok found '29346414.0000000', expected '29346414.0000000', error '0.0000000'

Test #12:

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

input:

216
9573 7015
9508 7159
9409 7352
9380 7407
9371 7424
9321 7511
9294 7558
9275 7590
9270 7598
9180 7739
9112 7841
9075 7894
8977 8027
8913 8109
8797 8250
8780 8269
8704 8355
8640 8425
8612 8454
8596 8470
8594 8473
8560 8507
8479 8589
8431 8634
8372 8689
8340 8718
8105 8916
8034 8971
7977 9015
7840 9...

output:

36377905.149990767240524

result:

ok found '36377905.1499908', expected '36377905.1499908', error '0.0000000'

Test #13:

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

input:

406
8048 1039
8053 1043
8176 1141
8299 1247
8324 1267
8352 1293
8379 1318
8416 1351
8422 1358
8472 1405
8479 1412
8499 1431
8510 1443
8517 1448
8517 1449
8563 1496
8606 1540
8616 1551
8664 1601
8673 1610
8686 1625
8703 1643
8744 1689
8755 1701
8763 1711
8785 1737
8797 1750
8928 1910
8951 1939
8982 1...

output:

20479513.012126922607422

result:

ok found '20479513.0121269', expected '20479513.0121269', error '0.0000000'

Test #14:

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

input:

594
4745 8
4753 8
4784 7
4806 6
4836 4
4846 4
4921 3
4986 2
5042 2
5114 4
5120 3
5233 7
5347 14
5350 14
5359 15
5415 19
5427 20
5455 22
5483 25
5493 27
5494 26
5496 27
5515 28
5521 29
5522 29
5587 36
5621 41
5670 47
5674 48
5691 50
5732 56
5802 67
5821 70
5837 73
5843 73
5869 78
5916 87
5953 93
5973...

output:

13084325.895022276788950

result:

ok found '13084325.8950223', expected '13084325.8950223', error '0.0000000'

Test #15:

score: 0
Accepted
time: 3ms
memory: 3844kb

input:

774
9982 4596
9983 4615
9983 4619
9984 4624
9984 4627
9985 4645
9988 4680
9989 4700
9993 4765
9995 4823
9995 4826
9996 4851
9996 4884
9997 4896
9997 4922
9998 4993
9998 5000
9997 5086
9997 5105
9996 5116
9997 5117
9996 5157
9995 5158
9995 5162
9992 5236
9992 5250
9991 5257
9989 5288
9987 5327
9983 5...

output:

16822524.668747767806053

result:

ok found '16822524.6687478', expected '16822524.6687478', error '0.0000000'

Test #16:

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

input:

4
0 0
10000 0
10000 10000
0 10000

output:

100000000.000000000000000

result:

ok found '100000000.0000000', expected '100000000.0000000', error '0.0000000'

Test #17:

score: 0
Accepted
time: 16ms
memory: 3912kb

input:

1999
10000 206
1 206
10000 207
1 207
10000 208
1 208
10000 209
1 209
10000 210
1 210
10000 211
1 211
10000 212
1 212
10000 213
1 213
10000 214
1 214
10000 215
1 215
10000 216
1 216
10000 217
1 217
10000 218
1 218
10000 219
1 219
10000 220
1 220
10000 221
1 221
10000 222
1 222
10000 223
1 223
10000 2...

output:

5000.500000000000000

result:

ok found '5000.5000000', expected '5000.5000000', error '0.0000000'

Test #18:

score: 0
Accepted
time: 16ms
memory: 3912kb

input:

1999
2558 4070
7558 9067
2555 4075
7555 9072
2552 4080
7552 9077
2549 4085
7549 9082
2546 4090
7546 9087
2543 4095
7543 9092
2540 4100
7540 9097
2537 4105
7537 9102
2534 4110
7534 9107
2531 4115
7531 9112
2528 4120
7528 9117
2525 4125
7525 9122
2522 4130
7522 9127
2519 4135
7519 9132
2516 4140
7516 ...

output:

20015.527544070035219

result:

ok found '20015.5275441', expected '20015.5275441', error '0.0000000'

Test #19:

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

input:

1999
8044 3034
8041 3044
8038 3043
8035 3053
8032 3052
8029 3062
8026 3061
8023 3071
8020 3070
8017 3080
8014 3079
8011 3089
8008 3088
8005 3098
8002 3097
7999 3107
7996 3106
7993 3116
7990 3115
7987 3125
7984 3124
7981 3134
7978 3133
7975 3143
7972 3142
7969 3152
7966 3151
7963 3161
7960 3160
7957 ...

output:

12416.622345803887583

result:

ok found '12416.6223458', expected '12416.6223458', error '0.0000000'

Test #20:

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

input:

3
1664 1839
5145 767
5644 8714

output:

14099217.500000000000000

result:

ok found '14099217.5000000', expected '14099217.5000000', error '0.0000000'

Test #21:

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

input:

4
5094 2585
5154 4865
5972 9655
5003 6086

output:

388962.331699395319447

result:

ok found '388962.3316994', expected '388962.3316994', error '0.0000000'

Test #22:

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

input:

5
3839 2462
6450 9731
917 6915
2220 5164
1430 1649

output:

15630841.306313807144761

result:

ok found '15630841.3063138', expected '15630841.3063138', error '0.0000000'

Test #23:

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

input:

6
4474 1457
4905 3089
7554 5776
6426 6077
4616 4542
3028 1491

output:

3517836.371496747247875

result:

ok found '3517836.3714967', expected '3517836.3714967', error '0.0000000'

Test #24:

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

input:

7
5319 5082
5280 6009
5900 8273
4111 5641
2346 6076
4674 4589
5948 4865

output:

920101.569259552401491

result:

ok found '920101.5692596', expected '920101.5692596', error '0.0000000'

Test #25:

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

input:

8
4096 3756
5382 4371
7186 1749
9632 4602
9758 4704
7149 6803
3563 8911
1013 2622

output:

20333963.765386167913675

result:

ok found '20333963.7653862', expected '20333963.7653862', error '0.0000000'

Test #26:

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

input:

9
7720 2038
8160 2661
6427 4528
7007 5869
7399 6513
2037 4071
995 3028
3176 881
5040 1874

output:

16379711.105319684371352

result:

ok found '16379711.1053197', expected '16379711.1053197', error '0.0000000'

Test #27:

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

input:

10
5757 1393
8096 4772
7059 5458
6743 5903
2827 8013
2719 6272
4013 5299
4392 5065
1849 2006
4954 4503

output:

6259308.473179914057255

result:

ok found '6259308.4731799', expected '6259308.4731799', error '0.0000000'

Test #28:

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

input:

11
6380 2640
6053 3857
8539 3296
7275 6299
6595 7559
5977 7236
2481 7189
1352 7020
2354 6448
3042 3511
5262 3499

output:

2610035.089641427621245

result:

ok found '2610035.0896414', expected '2610035.0896414', error '0.0000000'

Test #29:

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

input:

12
4742 5314
3575 5937
1908 5632
3425 2791
4749 4476
4329 252
7368 4691
8318 6692
8011 7335
5673 5882
4724 6947
3994 8628

output:

474170.161448199534789

result:

ok found '474170.1614482', expected '474170.1614482', error '0.0000000'

Test #30:

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

input:

13
5477 9803
2323 7271
2200 6085
3516 5451
4596 5080
458 5740
1946 3432
5670 1483
5233 4897
6551 6066
5538 5823
5338 6304
5707 9308

output:

631741.317085074726492

result:

ok found '631741.3170851', expected '631741.3170851', error '0.0000000'

Test #31:

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

input:

14
4512 6057
2092 8704
1615 5835
3126 4434
1535 2397
1893 1846
4686 2290
5217 3920
5402 4267
5492 4465
8382 1789
9291 4246
5608 9153
5332 7607

output:

4505176.498228449374437

result:

ok found '4505176.4982284', expected '4505176.4982284', error '0.0000000'

Test #32:

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

input:

15
4466 5396
1705 4917
3305 4526
1737 3617
3847 4013
5854 2118
5870 2160
6816 2334
7348 1946
6136 4410
8998 4850
9815 5079
7271 8684
6067 9279
5028 6591

output:

2398614.676149465143681

result:

ok found '2398614.6761495', expected '2398614.6761495', error '0.0000000'

Test #33:

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

input:

16
2696 3357
3395 2997
3757 2086
4827 84
6762 1878
7658 1889
7639 4233
7259 4355
6253 5691
7394 7382
6070 8938
5062 5341
3877 7728
3529 8177
1772 8147
1581 2562

output:

5453.740360503114061

result:

ok found '5453.7403605', expected '5453.7403605', error '0.0000000'

Test #34:

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

input:

17
9639 5654
8700 7119
6752 8284
6658 9048
6061 9043
5240 6097
5166 6416
5085 8596
4880 5732
3324 8722
3573 6800
2159 7089
3636 5438
4221 4774
3430 1818
5118 257
5178 431

output:

8859629.518314387649298

result:

ok found '8859629.5183144', expected '8859629.5183144', error '0.0000000'

Test #35:

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

input:

18
4684 4937
1396 4109
1880 3238
2541 811
3585 601
4837 4007
4735 1936
6971 2430
5309 4810
9367 4665
5106 5027
8195 6885
6551 9079
5139 7637
4917 6186
4783 7309
2686 8721
1754 7471

output:

125428.753615232068114

result:

ok found '125428.7536152', expected '125428.7536152', error '0.0000000'

Test #36:

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

input:

16
5000 4332
4332 5000
5000 5668
5668 5000
5000 1761
1761 5000
5000 8239
8239 5000
8914 5000
5000 8914
1086 5000
5000 1086
8205 5000
5000 8205
1795 5000
5000 1795

output:

6521992.750000000000000

result:

ok found '6521992.7500000', expected '6521992.7500000', error '0.0000000'

Test #37:

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

input:

2000
5411 5000
5000 5411
4589 5000
5000 4589
5405 5000
5000 5405
4595 5000
5000 4595
5335 5000
5000 5335
4665 5000
5000 4665
5328 5000
5000 5328
4672 5000
5000 4672
5302 5000
5000 5302
4698 5000
5000 4698
5287 5000
5000 5287
4713 5000
5000 4713
5283 5000
5000 5283
4717 5000
5000 4717
5278 5000
5000 ...

output:

63.000000000000000

result:

ok found '63.0000000', expected '63.0000000', error '0.0000000'

Test #38:

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

input:

17
253 449
231 314
60 302
192 231
115 70
230 139
248 89
269 126
304 104
300 141
376 119
332 169
485 216
356 250
464 395
440 408
299 287

output:

2823.585557503602104

result:

ok found '2823.5855575', expected '2823.5855575', error '0.0000000'

Test #39:

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

input:

12
1 0
3 0
3 1
5 1
5 3
4 3
4 5
2 5
2 4
0 4
0 2
1 2

output:

1.000000000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #40:

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

input:

32
65 44
446 37
456 81
115 82
70 424
417 449
442 152
160 116
117 376
381 399
396 194
208 161
170 333
344 343
364 231
265 216
258 266
321 275
316 293
223 285
237 191
386 217
361 366
153 342
190 141
419 175
401 426
95 395
149 95
471 132
450 474
33 441

output:

15933.326011304447093

result:

ok found '15933.3260113', expected '15933.3260113', error '0.0000000'

Test #41:

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

input:

12
31 458
32 409
82 416
87 196
25 186
36 141
158 144
172 196
125 201
119 421
179 425
176 471

output:

0.000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #42:

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

input:

43
428 479
366 477
287 466
197 439
157 409
124 364
90 305
60 217
52 147
60 80
98 47
164 30
228 22
324 20
362 27
425 44
457 65
469 89
472 126
457 155
436 172
412 171
393 152
388 120
382 82
351 67
283 66
247 68
208 75
174 85
150 108
134 147
138 195
158 264
184 319
229 371
275 404
326 421
386 423
440 4...

output:

9574.730709476949414

result:

ok found '9574.7307095', expected '9574.7307095', error '0.0000000'

Test #43:

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

input:

29
132 465
107 334
123 242
114 128
124 50
165 40
177 88
194 170
186 208
190 273
197 332
189 371
189 412
226 425
285 410
286 364
278 312
241 295
215 294
204 283
200 261
208 238
250 234
319 258
332 301
341 381
317 431
220 471
162 472

output:

16853.803655815285310

result:

ok found '16853.8036558', expected '16853.8036558', error '0.0000000'

Test #44:

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

input:

16
204 449
280 336
224 287
210 357
92 346
103 129
248 124
238 239
301 314
352 248
276 176
354 85
492 273
453 324
379 269
227 464

output:

0.000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #45:

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

input:

76
148 257
231 232
302 197
344 133
331 91
268 61
175 59
126 95
136 139
166 161
240 159
267 126
238 102
197 114
190 133
166 121
170 100
197 86
243 86
281 110
287 143
259 175
179 191
130 162
97 105
113 66
158 36
229 29
348 33
411 75
422 141
394 197
302 260
187 282
98 316
83 387
111 454
232 463
329 460...

output:

11552.254374559051939

result:

ok found '11552.2543746', expected '11552.2543746', error '0.0000000'

Test #46:

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

input:

43
369 304
284 263
213 241
151 202
116 156
125 110
161 72
219 61
331 55
393 82
419 139
412 174
383 194
320 201
249 183
241 145
276 131
292 151
319 163
368 145
361 116
301 98
238 98
159 117
178 185
241 218
325 234
432 273
451 334
395 400
275 424
166 418
101 372
89 312
140 275
193 281
206 312
183 316
...

output:

0.000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #47:

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

input:

14
0 0
10 0
20 10
20 0
30 0
30 50
20 50
20 40
0 50
0 40
20 30
0 30
0 20
20 20

output:

225.000000000000000

result:

ok found '225.0000000', expected '225.0000000', error '0.0000000'

Test #48:

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

input:

14
80 20
100 20
100 30
80 30
100 40
100 50
80 40
80 50
70 50
70 0
80 0
80 10
90 0
100 0

output:

250.000000000000000

result:

ok found '250.0000000', expected '250.0000000', error '0.0000000'

Test #49:

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

input:

6
0 10
10 10
10 0
30 10
20 10
20 20

output:

0.000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #50:

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

input:

6
0 0
1731 1971
6924 0
6924 7884
3462 3942
0 7884

output:

0.000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #51:

score: 0
Accepted
time: 11ms
memory: 3896kb

input:

1997
3908 7186
4995 5010
3369 8248
3742 7495
3196 8560
2914 9075
3115 8666
3503 7878
3121 8572
4518 5914
3643 7523
4364 6181
4836 5304
2850 8959
3474 7801
2825 8973
4059 6705
3798 7143
2927 8667
4887 5194
3881 6907
3365 7776
3907 6854
4938 5105
3879 6898
4032 6630
3235 7915
4167 6367
3342 7681
3651 ...

output:

0.000030245953798

result:

ok found '0.0000302', expected '0.0000302', error '0.0000000'

Test #52:

score: 0
Accepted
time: 11ms
memory: 4000kb

input:

2000
5522 5219
8387 6423
8073 6292
5769 5326
5134 5057
7832 6210
9500 6938
5728 5314
6398 5607
8840 6684
8386 6486
5941 5413
6212 5534
7948 6320
7368 6082
7458 6130
8630 6673
5778 5365
8910 6840
6535 5729
8580 6706
7937 6401
9333 7091
6070 5523
6445 5709
6269 5626
5824 5408
9288 7127
8332 6658
8308 ...

output:

0.000211900552731

result:

ok found '0.0002119', expected '0.0002119', error '0.0000000'

Test #53:

score: 0
Accepted
time: 11ms
memory: 3996kb

input:

1998
4932 8589
4943 7827
4968 6473
4913 8891
4991 5372
4950 6812
4959 6459
4939 7033
4981 5633
4921 7622
4894 8476
4998 5063
4949 6492
4965 5978
4910 7511
4936 6785
4926 6948
4943 6363
4971 5676
4923 6712
4968 5705
4918 6801
4816 8882
4873 7459
4998 5038
4962 5706
4746 9708
4954 5844
4807 8476
4787 ...

output:

0.074952258259867

result:

ok found '0.0749523', expected '0.0749523', error '0.0000000'

Test #54:

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

input:

50
5015 4997
5093 4991
5022 5000
5037 5000
5087 5022
5009 5003
5006 5003
5042 5050
5055 5070
5047 5061
5003 5005
5036 5079
5010 5022
5011 5040
5006 5065
5000 5047
4993 5029
4957 5077
4986 5025
4954 5075
4962 5044
4916 5032
4929 5026
4962 5001
4933 4995
4987 4999
4978 4992
4959 4972
4964 4973
4942 49...

output:

0.007300534995466

result:

ok found '0.0073005', expected '0.0073005', error '0.0000000'

Test #55:

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

input:

79
4986 5084
4986 5070
4985 5072
4985 5049
4995 5016
4972 5076
4969 5083
4970 5075
4988 5024
4983 5031
4963 5063
4980 5034
4961 5065
4967 5055
4975 5040
4942 5080
4956 5053
4944 5063
4973 5028
4932 5068
4998 5002
4952 5046
4991 5008
4976 5021
4991 5007
4933 5044
4993 5004
4952 5027
4960 5021
4961 50...

output:

52.376553770125611

result:

ok found '52.3765538', expected '52.3765538', error '0.0000000'

Test #56:

score: 0
Accepted
time: 13ms
memory: 3932kb

input:

1998
1917 1090
1994 1130
1949 1060
1988 1105
2013 1088
1995 1051
2018 1081
2017 1075
1990 1012
2028 1056
2061 1050
2025 988
2054 1014
2063 1026
2073 1039
2053 1010
2090 1056
2055 1007
2068 984
2114 1039
2077 956
2130 934
2173 939
2184 950
2190 950
2174 925
2199 950
2170 891
2184 905
2217 932
2232 93...

output:

648.916144486771373

result:

ok found '648.9161445', expected '648.9161445', error '0.0000000'

Test #57:

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

input:

8
10000 5000
6290 9098
4839 9872
4493 5089
0 5000
1303 4598
6845 4019
9531 4513

output:

19096233.353069297969341

result:

ok found '19096233.3530693', expected '19096233.3530693', error '0.0000000'

Test #58:

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

input:

12
9655 4437
10000 5000
7601 7069
7417 5094
6234 9740
5647 5823
2952 9902
0 5000
1077 2483
1484 1006
5194 4762
5906 4669

output:

0.000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #59:

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

input:

102
8183 8502
8121 5436
8115 5246
7984 5519
7960 5756
7651 9056
7344 6661
6964 6004
6859 6357
6796 6201
6174 6993
6018 7554
4943 5819
4682 9215
4340 5133
4265 9301
4091 6200
4056 7421
3879 9768
3151 8458
3084 5033
2972 8393
2878 5776
2846 9118
2741 5004
2670 7439
2573 5540
2176 7512
1986 9889
1888 9...

output:

0.000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #60:

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

input:

202
7712 8006
7061 5151
7042 5648
6678 6438
6317 5458
6059 6865
5961 6359
5737 6582
5652 8116
5534 8511
5441 8740
5383 6591
5353 6949
5179 9463
5048 8393
5040 7166
4804 6848
4702 7324
4630 5983
4553 5243
4238 8581
4115 5462
4084 7836
4076 8750
4015 7738
4001 7981
3945 9486
3730 5060
3543 9931
3496 6...

output:

0.000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #61:

score: 0
Accepted
time: 3ms
memory: 3784kb

input:

1002
2414 9545
2413 7915
2325 7087
2274 8223
2235 9807
2148 5400
2130 7668
2130 8701
2112 8289
2097 9514
2094 8965
2090 5062
2089 8687
2062 9783
2025 9987
2011 6627
2008 5825
1995 5049
1986 6219
1956 6644
1931 5762
1899 9376
1877 5902
1849 6083
1847 6166
1842 6903
1829 9005
1806 5550
1794 8579
1780 ...

output:

0.000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #62:

score: 0
Accepted
time: 11ms
memory: 3924kb

input:

1995
5769 294
5786 3987
5789 618
5814 35
5831 3023
5840 1612
5853 4924
5902 4849
5910 3592
5928 2236
5944 3280
5946 4848
6003 674
6009 3876
6035 990
6043 1306
6043 3462
6058 2385
6066 1654
6070 3176
6085 623
6090 4658
6097 1213
6115 1672
6115 2000
6129 4063
6130 3879
6148 576
6176 1065
6179 3641
619...

output:

0.000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'