QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#307525#7310. Circular SectorsmshcherbaAC ✓1169ms21760kbC++207.8kb2024-01-18 19:31:502024-01-18 19:31:50

Judging History

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

  • [2024-01-18 19:31:50]
  • 评测
  • 测评结果:AC
  • 用时:1169ms
  • 内存:21760kb
  • [2024-01-18 19:31:50]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long double db;

const db EPS = 1e-12;
const db EPS_EVENTS = 1e-9;
const db PI = acos(-1.0);

struct Pt
{
	db x, y;
	Pt operator+(const Pt& p) const
	{
		return {x + p.x, y + p.y};
	}
	Pt operator-(const Pt& p) const
	{
		return {x - p.x, y - p.y};
	}
	Pt operator*(db d) const
	{
		return {x * d, y * d};
	}
	Pt operator/(db d) const
	{
		return {x / d, y / d};
	}
};

db sq(const Pt& p)
{
	return p.x * p.x + p.y * p.y;
}

db abs(const Pt& p)
{
	return sqrt(sq(p));
}

int sgn(db x)
{
	return (EPS < x) - (x < -EPS);
}

Pt perp(const Pt& p)
{
	return {-p.y, p.x};
}

db dot(const Pt& p, const Pt& q)
{
	return p.x * q.x + p.y * q.y;
}

db cross(const Pt& p, const Pt& q)
{
	return p.x * q.y - p.y * q.x;
}

db orient(const Pt& p, const Pt& q, const Pt& r)
{
	return cross(q - p, r - p) / abs(q - p);
}

ostream& operator<<(ostream& os, const Pt& p)
{
	return os << "(" << p.x << "," << p.y << ")";
}

struct Line
{
	Pt n;
	db c;
	Line(const Pt& p, const Pt& q):
		n(perp(q - p)), c(-dot(n, p)) {}
	db side(const Pt& p) const
	{
		return dot(n, p) + c;
	}
	db sqDist(const Pt& p) const
	{
		return side(p) * side(p) / (db)sq(n);
	}
	Pt proj(const Pt& p) const
	{
		return p - n * side(p) / sq(n);
	}
};

bool parallel(const Line& l1, const Line& l2)
{
	return sgn(cross(l1.n, l2.n)) == 0;
}

Pt inter(const Line& l1, const Line& l2)
{
	db d = cross(l1.n, l2.n);
	assert(sgn(d) != 0);
	return perp(l2.n * l1.c - l1.n * l2.c) / d;
}

bool inDisk(const Pt& a, const Pt& b,
	const Pt& p)
{
	return sgn(dot(a - p, b - p)) <= 0;
}

bool onSegment(const Pt& a, const Pt& b,
	const Pt& p)
{
	return sgn(orient(a, b, p)) == 0
		&& inDisk(a, b, p);
}

vector<Pt> circleLine(const Pt& o, db r,
	const Line& l)
{
	db h2 = r * r - l.sqDist(o);
	if (sgn(h2) == -1)
		return {};
	Pt p = l.proj(o);
	if (sgn(h2) == 0)
		return {p};
	Pt h = perp(l.n) * sqrt(h2) / abs(l.n);
	return {p - h, p + h};
}

vector<Pt> circleCircle(const Pt& o1, db r1,
	const Pt& o2, db r2)
{
	Pt d = o2 - o1;
	db d2 = sq(d);
	if (sgn(d2) == 0)
	{
		return {};
	}
	db pd = (d2 + r1 * r1 - r2 * r2) / 2;
	db h2 = r1 * r1 - pd * pd / d2;
	if (sgn(h2) == -1)
		return {};
	Pt p = o1 + d * pd / d2;
	if (sgn(h2) == 0)
		return {p};
	Pt h = perp(d) * sqrt(h2 / d2);
	return {p - h, p + h};
}

bool strictlyIncreasing(db a, db b, db c)
{
	return sgn(a - b) < 0 && sgn(b - c) < 0;
}

struct Sector
{
	Pt o;
	db r, s, theta;
	Pt p1, p2;
};

vector<Sector> sectors;
vector<Line> lines;

struct Event
{
	db x;
	int i, j, k;
	bool operator<(const Event& event) const
	{
		return x < event.x - EPS_EVENTS;
	}
};

db getY(const PII& ij, db x)
{
	const auto& [i, j] = ij;
	if (j == 0)
	{
		const Line& l = lines[i];
		return -(l.n.x * x + l.c) / l.n.y;
	}
	const Pt& o = sectors[i].o;
	db r = sectors[i].r;
	return o.y + j * sqrt(max((db)0.0, r * r - (x - o.x) * (x - o.x)));
};

struct Comparator
{
	static db x;
	bool operator() (const PII& a, const PII& b) const
	{
		int dy = sgn(getY(a, x) - getY(b, x));
		if (dy != 0)
			return dy < 0;
		return a < b;
	}
} cmp;

db Comparator::x;

db getAreaOfCirclePart(db r, db x)
{
	db co = clamp(x / r, (db)-1.0, (db)1.0);
	db alpha = acos(co);
	return (PI - alpha + co * sqrt(1 - co * co)) * r * r / 2;	
}

void solve(int n)
{
	sectors.resize(n);
	lines.clear();
	VI linesBalances;
	for (auto& [o, r, s, theta, p1, p2] : sectors)
	{
		cin >> o.x >> o.y >> r >> s >> theta;
		p1 = {o.x + r * cos(s), o.y + r * sin(s)};
		linesBalances.PB(sgn(cos(s)));
		p2 = {o.x + r * cos(s + theta), o.y + r * sin(s + theta)};
		linesBalances.PB(-sgn(cos(s + theta)));
		lines.PB({o, p1});
		lines.PB({o, p2});
	}
	vector<Event> events;
	FOR(i, 0, n)
	{
		const auto& [o, r, s, theta, p1, p2] = sectors[i];
		if (strictlyIncreasing(s, PI, s + theta)
			|| strictlyIncreasing(s, 3 * PI, s + theta))
		{
			events.PB({o.x - r, i, -1, 1});
			events.PB({o.x - r, i, 1, 1});
		}
		if (strictlyIncreasing(s, 2 * PI, s + theta))
		{
			events.PB({o.x + r, i, -1, -1});
			events.PB({o.x + r, i, 1, -1});
		}
		events.PB({p1.x, i, -1, 1});
		if (sgn(p1.y - o.y) > 0
			|| (sgn(p1.y - o.y) == 0 && sgn(p1.x - o.x) > 0))
		{
			events.back().j *= -1;
			events.back().k *= -1;
		}
		events.PB({p2.x, i, -1, -1});
		if (sgn(p2.y - o.y) > 0
			|| (sgn(p2.y - o.y) == 0 && sgn(p2.x - o.x) < 0))
		{
			events.back().j *= -1;
			events.back().k *= -1;
		}
		int idxLine = 2 * i;
		for (const Pt& p : {p1, p2})
		{
			assert(sgn(p.x - o.x) != 0);
			bool toLeft = sgn(o.x - p.x) < 0;
			events.PB({o.x, idxLine, 0, toLeft ? 1 : -1});
			events.PB({p.x, idxLine, 0, toLeft ? -1 : 1});
			idxLine++;
		}
		FOR(j, 0, n)
		{
			if (j == i)
				continue;
			const auto& sector = sectors[j];
			if (j < i)
			{
				vector<Pt> cc = circleCircle(o, r, sector.o, sector.r);
				for (const Pt& q : cc)
				{
					events.PB({q.x, 0, 0, 0});
				}
			}
			idxLine = 2 * j;
			for (const Pt& p : {sector.p1, sector.p2})
			{
				vector<Pt> cl = circleLine(o, r, lines[idxLine]);
				for (const Pt& q : cl)
				{
					if (onSegment(sector.o, p, q))
					{
						events.PB({q.x, 0, 0, 0});
					}
				}
				idxLine++;
			}
		}
	}
	FOR(i, 0, 2 * n)
	{
		Pt o1 = sectors[i / 2].o;
		Pt pi = i % 2 == 0 ? sectors[i / 2].p1 : sectors[i / 2].p2;
		FOR(j, 0, i)
		{
			if (i / 2 == j / 2 || parallel(lines[i], lines[j]))
				continue;
			Pt o2 = sectors[j / 2].o;
			Pt pj = j % 2 == 0 ? sectors[j / 2].p1 : sectors[j / 2].p2;
			Pt q = inter(lines[i], lines[j]);
			if (onSegment(o1, pi, q)
				&& onSegment(o2, pj, q))
			{
				events.PB({q.x, 0, 0, 0});
			}
		}
	}
	set<PII, Comparator> curves;
	sort(ALL(events));
	db ans = 0;
	for(int idxEvent = 0; ;)
	{
		set<PII> del, add;
		int ptr = idxEvent;
		while (ptr < SZ(events) && !(events[idxEvent] < events[ptr]))
		{
			PII cur = {events[ptr].i, events[ptr].j};
			if (events[ptr].k == -1)
				del.insert(cur);
			else if (events[ptr].k == 1)
				add.insert(cur);
			ptr++;
		}
		for (const PII& ij : del)
		{
			curves.erase(ij);
		}
		if (ptr == SZ(events))
			break;
		db xl = events[idxEvent].x, xr = events[ptr].x;
		Comparator::x = (xl + xr) / 2;
		vector<PII> badOrder;
		for (auto it = curves.begin(); it != curves.end() && next(it) != curves.end(); it++)
		{
			auto nit = next(it);
			while (!cmp(*it, *nit))
			{
				badOrder.PB(*nit);
				curves.erase(nit);
				nit = next(it);
				if (nit == curves.end())
					break;
			}
		}
		for (const PII& ij : badOrder)
			curves.insert(ij);
		for (const PII& ij : add)
		{
			curves.insert(ij);
		}
		int bal = 0;
		for (const PII& ij : curves)
		{
			const auto& [i, j] = ij;
			int deltaBal = j == 0 ? linesBalances[i] : -j;
			assert(bal >= 0);
			if (bal == 0 || bal + deltaBal == 0)
			{
				db area;
				if (j == 0)
				{
					area = (getY(ij, xl) + getY(ij, xr)) * (xr - xl) / 2;
				}
				else
				{
					const Pt& o = sectors[i].o;
					db r = sectors[i].r;
					area = j * (getAreaOfCirclePart(r, xr - o.x) - getAreaOfCirclePart(r, xl - o.x)) + o.y * (xr - xl);
				}
				ans -= deltaBal * area;
			}
			bal += deltaBal;
		}
		assert(bal == 0);
		idxEvent = ptr;
	}
	cout << ans << "\n";
}

int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	cout << fixed << setprecision(15);
	int n;
	while (cin >> n)
	{
		solve(n);
	}
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3872kb

input:

2
-3 -5 5 0.705 0.217
-5 1 4 3.070 4.136
1
-4 -4 1 0.485 2.260
3
4 4 4 4.266 4.673
2 -4 5 0.353 5.565
-2 1 3 3.974 0.207

output:

35.800500000000000
1.130000000000000
106.444931438703580

result:

ok 3 numbers

Test #2:

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

input:

2
-2 -1 5 2.250 0.555
-3 0 2 2.189 0.788
2
-5 1 5 0.432 1.643
3 5 5 4.779 2.014
2
2 0 3 4.194 2.691
4 -3 4 0.998 5.376
2
-3 1 4 5.841 2.968
-4 -3 2 4.151 4.029
2
4 -1 5 2.416 2.385
5 0 3 5.315 2.683
2
-2 0 2 3.972 1.255
2 -5 2 0.912 5.211
2
1 0 4 2.826 3.794
-2 -3 1 3.335 3.836
2
-5 4 2 2.496 2.273
...

output:

6.937500000000000
45.712500000000000
43.533920893527539
31.802000000000000
41.886000000000000
12.932000000000000
31.713102368390353
9.890000000000000
3.811500000000000
26.790000000000000
37.187500000000000
10.700500000000000
31.423500000000000
47.664000000000000
25.456500000000000
54.013595092918764...

result:

ok 250 numbers

Test #3:

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

input:

3
1 -1 5 3.089 5.717
-2 0 2 4.806 3.257
0 -3 2 5.069 3.049
3
-2 -4 2 4.616 2.875
2 -2 4 5.798 3.097
-1 2 1 0.064 5.418
3
-1 1 2 4.105 3.883
0 5 4 1.936 4.292
2 -5 2 0.278 4.486
3
3 -5 5 3.208 4.696
-2 -4 3 3.609 0.906
-2 4 3 3.796 4.334
3
0 -1 1 4.313 0.711
2 -2 1 2.962 0.344
-4 2 5 2.524 3.043
3
-1...

output:

74.157879726552894
33.235000000000000
47.749461461744601
82.280000000000000
38.565000000000000
57.287500000000000
16.887500000000000
30.812466324073254
18.266137364384574
43.264634755237459
42.494217510621977
26.132749175803262
26.404500000000000
30.106728114671796
48.937000000000000
23.139500000000...

result:

ok 166 numbers

Test #4:

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

input:

4
4 3 4 1.727 2.114
-5 3 2 5.010 2.690
-1 1 5 4.078 2.852
1 5 5 2.974 4.884
4
3 4 1 5.626 2.021
2 -4 1 1.241 0.231
4 -4 5 0.323 5.472
-2 5 2 2.648 1.031
4
-1 -1 2 0.156 3.062
2 2 1 1.127 4.124
5 3 5 1.105 5.179
4 2 3 3.363 4.235
4
-2 -3 3 1.013 4.047
0 -5 5 1.829 4.952
-4 0 5 2.029 4.410
3 -1 4 1.40...

output:

89.059592091965933
71.472500000000000
72.359337599729827
126.255569920522023
53.321194904763857
59.877062378554662
47.616876770028659
66.382775434501406
26.793763102702925
32.341500000000000
139.853466960893417
81.663107773503010
102.706053155319407
81.919837964614136
30.252901352145075
88.100998126...

result:

ok 125 numbers

Test #5:

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

input:

5
-4 -1 4 2.566 3.253
1 -1 2 3.826 4.000
1 2 5 4.113 3.814
-1 -4 2 4.386 3.959
-1 -2 1 5.785 3.937
5
4 2 4 2.417 0.945
-5 -3 3 4.946 5.172
2 -2 2 2.380 0.205
3 3 4 0.766 4.402
-2 4 5 3.442 4.263
5
0 -4 3 5.172 0.603
-4 -5 3 1.321 3.688
-5 1 4 4.363 3.784
-5 -1 4 2.943 2.791
-2 5 3 5.292 5.765
5
-5 -...

output:

79.693585184955934
91.736875590339164
79.436470427630910
77.453260899735851
98.285986593755338
71.089224340747053
7.725500000000000
103.276610901060772
18.876111372247369
83.851724321134310
37.132095585543558
80.144201783696144
100.607500000000000
89.227847271325908
94.924728487345116
24.35600000000...

result:

ok 100 numbers

Test #6:

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

input:

10
4 4 4 2.043 4.661
0 -2 3 4.728 5.010
1 5 5 0.478 2.500
1 2 4 3.314 2.904
4 -4 5 3.408 5.869
-3 1 5 0.644 2.968
2 0 4 5.532 0.421
2 -3 1 3.492 0.855
-3 -3 5 4.475 4.896
-4 -1 3 0.873 1.815
10
-2 -1 3 4.786 3.714
-4 -3 1 0.155 4.804
-1 -5 3 4.225 2.500
-4 -1 4 5.536 3.954
4 -2 4 5.516 2.204
-3 2 4 ...

output:

217.462255720490279
137.080435157705904
68.280440686838588
81.674905544446753
161.394725071889036
109.854743305694669
88.851098028933561
149.663820955674471
141.260453837597516
150.828583153720500
103.530625418356815
80.042106264194868
135.587222368681931
124.154668157309515
142.296821200933604
136....

result:

ok 50 numbers

Test #7:

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

input:

9
6 -5 6 4.848 5.374
9 4 3 2.135 4.598
8 -4 6 4.443 5.157
0 5 9 3.605 1.226
7 -4 9 1.917 4.657
6 -7 8 3.621 0.258
3 3 4 1.955 5.563
-6 -5 5 3.174 3.778
-10 9 1 5.808 1.214
10
2 0 8 5.479 1.980
-3 -1 10 2.909 0.574
-8 -10 4 1.758 4.039
2 -6 9 5.761 4.499
1 1 2 0.115 0.897
-3 7 6 0.574 4.703
-4 5 6 0....

output:

340.572472199963770
423.411657030425522
188.493590961885124
663.645597577173430
237.474510029904444
435.602263268936953
426.132393829239040
393.573805742597425
204.877572258180112
211.300974323964095
159.246000000000000
84.711314252478468
65.409000000000000
288.210429276220969
53.787500000000000
323...

result:

ok 97 numbers

Test #8:

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

input:

10
-19 46 24 2.749 0.181
25 -35 45 5.805 4.054
-19 41 38 3.066 0.881
39 -15 22 5.876 4.537
-34 23 23 2.975 5.225
-21 -27 36 5.103 1.849
-43 -27 47 1.506 5.692
8 -12 16 2.217 3.584
-39 2 48 3.455 0.978
23 15 42 2.422 2.305
10
41 -31 32 2.089 3.004
-25 22 41 4.804 4.138
-25 32 37 0.576 3.483
-35 36 32...

output:

12052.406264363612751
8029.721602593827213
17841.160242547987655
8905.310278028087005
9364.474299758411492
11342.793063077791617
7432.277263249038263
4958.018309445385218
12178.815954973788252
12163.545508884978747
10152.091787750142028
5644.239555710109967
8047.133278497371945
10406.167543782263823...

result:

ok 50 numbers

Test #9:

score: 0
Accepted
time: 53ms
memory: 4240kb

input:

93
48 -38 55 2.613 0.385
28 53 75 4.293 2.033
88 33 4 3.991 5.533
11 57 6 4.203 2.347
95 71 11 4.082 3.258
-4 39 61 0.466 4.435
-28 -36 75 1.871 5.160
15 -42 18 2.512 3.285
-68 10 25 4.824 3.391
-61 -21 75 1.593 4.869
41 -30 36 0.436 3.602
-100 94 48 4.538 1.943
-1 19 73 1.400 1.056
-43 29 42 2.508 ...

output:

90187.884972229950002
95856.664895293357446
78262.905029265647137
76227.524853917551042
101278.184257132962721
89979.898975388800928
81706.668381387154106

result:

ok 7 numbers

Test #10:

score: 0
Accepted
time: 5ms
memory: 3848kb

input:

4
-46 6 35 0.448 0.600
-38 -36 29 2.044 0.247
87 -33 87 0.139 5.721
-22 -69 56 5.013 5.314
1
-16 11 41 4.997 5.257
10
-80 -53 86 4.687 1.234
-76 -66 64 4.487 2.231
-46 3 39 5.532 4.214
-16 -94 70 1.841 2.220
-66 98 2 4.388 5.140
1 53 15 2.496 0.741
79 79 79 2.831 2.307
-16 10 92 4.938 3.805
-98 65 7...

output:

28820.394977238745323
4418.508500000000001
33061.953463050660385
45686.056434966195095
12072.339439476245468
5985.184023385508815
50770.001552460580506
42946.205898987398875
20200.603769154651124
36999.657973594574191
4337.216000000000001
5574.280500000000000
35395.913270822017527
24095.705148067117...

result:

ok 89 numbers

Test #11:

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

input:

33
-20 33 3 4.628 3.531
-43 10 4 5.952 4.299
49 -32 7 4.523 5.619
31 -15 5 4.429 1.704
50 40 14 4.025 0.773
-44 -14 31 0.113 2.654
-48 -16 2 4.571 2.209
16 14 11 3.296 3.719
34 -7 17 5.346 2.974
6 -45 22 3.532 2.678
-45 -14 33 3.100 1.706
-30 42 43 2.729 3.312
44 16 46 1.660 2.278
40 44 1 3.442 3.05...

output:

15802.283167443217282
21353.722702477987145
17122.857671863148337
17218.507770068511967
20193.954959457001978
18206.933769756462098
16965.217283117565637
19853.432944954332676
18881.619820128014023
12897.384431902637525
17739.729509985425572
20560.400965029885381
21622.473383571326016
21926.10674976...

result:

ok 14 numbers

Test #12:

score: 0
Accepted
time: 75ms
memory: 4400kb

input:

100
7 -66 7 3.504 5.074
-99 4 5 2.346 0.874
-68 93 47 4.684 5.490
89 46 87 4.250 0.385
46 79 87 2.659 5.715
-10 34 60 3.444 1.728
-82 69 83 4.298 2.078
-75 28 57 1.351 3.565
3 69 97 2.213 3.702
31 8 14 2.294 0.927
97 -23 65 1.493 1.414
55 47 45 2.466 4.113
-78 58 91 1.963 5.592
-97 49 84 4.659 1.604...

output:

96546.677629778880096
101085.301215711425023
104860.539882848343417
82685.042951206506558
87897.311215470075645

result:

ok 5 numbers

Test #13:

score: 0
Accepted
time: 282ms
memory: 19992kb

input:

500
1 -1 2 1.046 1.346
2 2 1 5.506 0.926
0 -2 2 5.468 3.385
0 -1 1 2.747 4.753
1 -2 2 1.805 5.313
2 0 2 1.543 3.123
2 2 2 1.604 0.801
0 -1 2 4.470 5.702
-1 2 2 1.725 4.320
1 1 1 3.526 5.798
2 0 2 2.157 3.678
-2 -2 2 3.575 0.905
-1 0 2 0.226 3.358
-1 0 2 0.655 0.196
-2 -2 1 4.774 0.375
-1 1 2 2.597 1...

output:

60.229840328281875

result:

ok found '60.2298403', expected '60.2298403', error '0.0000000'

Test #14:

score: 0
Accepted
time: 378ms
memory: 21760kb

input:

500
-3 -3 1 4.530 5.443
0 0 2 5.225 2.961
-2 3 3 0.553 3.603
2 3 1 3.997 3.909
3 -1 2 4.323 5.990
-3 -2 2 1.844 3.239
1 3 2 4.381 4.342
3 -3 2 5.542 4.859
1 1 3 5.812 2.058
1 0 3 4.137 5.145
-3 1 1 1.968 5.381
-3 0 1 5.792 5.585
3 -3 2 2.248 5.630
-2 -3 2 4.869 3.928
1 2 2 3.471 1.300
1 3 3 3.349 1....

output:

127.130359286166160

result:

ok found '127.1303593', expected '127.1303593', error '0.0000000'

Test #15:

score: 0
Accepted
time: 499ms
memory: 12880kb

input:

500
-2 -3 3 2.226 2.479
1 2 2 4.733 2.677
1 -1 4 1.639 0.785
0 -1 4 1.658 5.930
1 -1 2 0.839 0.766
1 4 2 5.733 3.355
1 -3 3 4.533 4.848
-3 0 4 2.815 5.893
1 -1 3 1.486 3.819
-1 4 2 3.573 2.616
-3 -1 2 1.991 2.342
-2 1 1 4.208 0.340
-4 -1 2 0.683 3.160
-1 2 4 4.469 2.477
3 -1 4 2.169 1.067
2 4 2 4.10...

output:

226.537907106410249

result:

ok found '226.5379071', expected '226.5379071', error '0.0000000'

Test #16:

score: 0
Accepted
time: 1074ms
memory: 12148kb

input:

500
1 -4 3 0.955 4.537
-6 -8 5 2.270 2.636
0 -8 6 2.832 0.248
5 -10 5 3.043 4.276
-8 7 5 0.498 5.868
4 2 1 0.859 5.246
5 2 6 3.800 0.490
-4 9 1 5.411 3.038
-7 -5 8 3.363 4.987
10 8 3 1.132 5.824
-5 1 1 4.473 5.142
3 8 3 1.239 0.169
9 8 10 1.572 3.165
-9 -6 1 5.417 0.808
-1 9 7 3.432 2.583
-5 -5 10 2...

output:

1290.241987371736060

result:

ok found '1290.2419874', expected '1290.2419874', error '0.0000000'

Test #17:

score: 0
Accepted
time: 1152ms
memory: 13508kb

input:

500
46 -1 28 2.976 5.503
-33 13 22 1.994 2.281
-8 -21 45 0.225 2.374
20 -16 50 1.846 4.885
-47 18 16 3.164 4.896
-50 -50 29 4.952 3.139
-30 -25 36 3.288 5.414
7 22 38 1.624 2.048
38 -42 36 4.738 4.037
45 -21 26 0.862 3.469
49 31 24 2.272 2.713
-20 33 49 5.034 2.956
22 -35 43 3.503 3.866
-44 -40 1 4....

output:

30725.286701907902048

result:

ok found '30725.2867019', expected '30725.2867019', error '0.0000000'

Test #18:

score: 0
Accepted
time: 1169ms
memory: 12928kb

input:

500
-30 -70 60 0.367 1.785
67 -49 33 4.479 4.251
49 69 23 3.739 3.621
-4 -79 78 5.223 4.472
76 -9 55 2.756 2.683
-92 68 46 4.485 1.664
-70 -99 83 2.169 2.224
-51 -44 37 5.120 2.789
77 1 14 1.546 0.104
31 1 5 4.427 3.778
95 -69 8 2.224 3.618
43 13 56 3.825 4.428
-22 -14 86 4.380 5.071
-32 -66 70 0.18...

output:

116138.459039379858382

result:

ok found '116138.4590394', expected '116138.4590394', error '0.0000000'

Test #19:

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

input:

1
-67 -57 95 5.527 5.362
5
-81 35 2 4.896 0.559
46 -93 2 2.108 2.103
-53 -83 90 3.952 4.883
-46 0 85 1.526 0.489
-59 49 72 4.560 2.778
2
23 67 64 5.290 2.804
89 27 23 0.733 5.058
5
20 62 53 4.727 5.415
24 52 62 4.999 4.205
-37 34 52 1.350 3.179
-43 76 83 0.130 5.985
-22 58 40 5.372 2.233
4
32 -96 83...

output:

24196.025000000000000
26709.166491608756520
6850.879799513089832
26614.846152865546440
11694.216934510925323
11487.744000000000001
327.184000000000000
9187.735767648827206
15880.670943644553640
27506.634468116434990
1788.125000000000000
10038.207000000000001
5846.010824241444503
22964.37432025549453...

result:

ok 167 numbers

Test #20:

score: 0
Accepted
time: 5ms
memory: 3852kb

input:

7
-47 -83 100 0.358 0.553
-71 97 98 1.499 3.915
17 -56 7 5.884 4.913
-18 20 52 3.900 3.718
8 29 60 0.002 2.098
-57 78 92 1.389 4.503
-60 45 98 5.668 4.783
7
-40 72 34 2.067 2.870
59 2 44 0.909 3.929
-83 15 62 3.224 3.054
-20 92 41 3.624 1.958
-64 44 67 1.002 3.405
70 -36 2 1.231 2.321
96 -87 10 1.92...

output:

38003.545741749672786
18615.980387945016840
30226.618185405656160
39138.651119082103975
39292.940077121883245
18460.238747751321100
23656.361897610342352
12845.720142760605110
37815.526148763525565
40040.124981319138776
43511.681965935410961
47180.773313263976906
27510.089072426358401
45552.13740957...

result:

ok 68 numbers

Test #21:

score: 0
Accepted
time: 640ms
memory: 12068kb

input:

500
4 1 1 5.923 2.552
3 5 2 0.653 3.552
1 2 3 2.725 5.745
1 -5 5 5.109 5.085
5 4 4 5.769 0.284
-3 -5 4 5.822 5.349
5 1 5 4.898 2.489
4 -3 4 3.888 5.049
3 0 4 5.361 0.398
-3 2 1 0.595 1.964
1 3 2 1.803 4.045
-2 -4 3 0.423 3.862
-2 1 2 2.705 0.690
-2 -3 3 2.682 2.185
-5 -5 2 3.279 0.115
3 -1 1 1.054 4...

output:

345.294170916386044

result:

ok found '345.2941709', expected '345.2941709', error '0.0000000'

Test #22:

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

input:

20
1 -35 10 3.746 3.231
24 52 90 3.896 3.562
-31 -61 75 3.823 2.329
29 -47 12 5.283 3.069
32 46 27 4.296 2.086
97 84 2 0.303 0.569
-1 97 5 4.166 5.644
71 -10 27 4.551 1.998
-16 -67 68 0.284 4.399
-90 -85 73 2.860 0.721
1 62 25 0.477 2.143
-46 -39 68 4.174 5.375
67 28 21 4.230 4.981
-22 -94 21 4.695 ...

output:

44998.723669597000100
26372.770547088456025
72184.119494019848382
47425.853590896986262
51623.399454197353656
33080.337986300135999
32731.071691809554892
45734.218398016426281
43352.520559914265473
57111.145591989256246
67496.696175494333836
28824.690509992232695
52331.899389117253165
42836.03087637...

result:

ok 32 numbers

Extra Test:

score: 0
Extra Test Passed