QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#545231#7310. Circular SectorsmshcherbaAC ✓502ms4556kbC++2010.2kb2024-09-03 02:59:002024-09-03 02:59:00

Judging History

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

  • [2024-09-03 02:59:00]
  • 评测
  • 测评结果:AC
  • 用时:502ms
  • 内存:4556kb
  • [2024-09-03 02:59:00]
  • 提交

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 vector<LL> VL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef long double db;

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

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);
}
// Returns `p` rotated counter-clockwise by `a`
Pt rot(const Pt& p, db a)
{
	db co = cos(a), si = sin(a);
	return {p.x * co - p.y * si,
		p.x * si + p.y * co};
}
// Returns `p` rotated counter-clockwise by 90 degrees
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;
}
// Returns the angle between `p` and `q` in [0, pi]
db angle(const Pt& p, const Pt& q)
{
	return acos(clamp(dot(p, q) / abs(p) /
		abs(q), (db)-1.0, (db)1.0));
}
db cross(const Pt& p, const Pt& q)
{
	return p.x * q.y - p.y * q.x;
}
// Positive if R is on the left side of PQ,
// negative on the right side,
// and zero if R is on the line containing PQ
db orient(const Pt& p, const Pt& q, const Pt& r)
{
	return cross(q - p, r - p) / abs(q - p);
}
// Checks if argument of `p` is in [-pi, 0)
bool half(const Pt& p)
{
	assert(sgn(p.x) != 0 || sgn(p.y) != 0);
	return sgn(p.y) == -1 ||
		(sgn(p.y) == 0 && sgn(p.x) == -1);
}
void polarSortAround(const Pt& o, vector<Pt>& v)
{
	sort(ALL(v), [o](Pt p, Pt q)
	{
		p = p - o;
		q = q - o;
		bool hp = half(p), hq = half(q);
		if (hp != hq)
			return hp < hq;
		int s = sgn(cross(p, q));
		if (s != 0)
			return s == 1;
		return sq(p) < sq(q);
	});
}
ostream& operator<<(ostream& os, const Pt& p)
{
	return os << "(" << p.x << "," << p.y << ")";
}
struct Line
{
	// Equation of the line is dot(n, p) + c = 0
	Pt n;
	db c;
	Line() {}
	Line (const Pt& _n, db _c): n(_n), c(_c) {}
	// n is the normal vector to the left of PQ
	Line(const Pt& p, const Pt& q):
		n(perp(q - p)), c(-dot(n, p)) {}
	// The "positive side": dot(n, p) + c > 0
	// The "negative side": dot(n, p) + c < 0
	db side(const Pt& p) const
	{
		return dot(n, p) + c;
	}
	db dist(const Pt& p) const
	{
		return abs(side(p)) / abs(n);
	}
	db sqDist(const Pt& p) const
	{
		return side(p) * side(p) / (db)sq(n);
	}
	Line perpThrough(const Pt& p) const
	{
		return {p, p + n};
	}
	bool cmpProj(const Pt& p, const Pt& q) const
	{
		return sgn(cross(p, n) - cross(q, n)) < 0;
	}
	Pt proj(const Pt& p) const
	{
		return p - n * side(p) / sq(n);
	}
	Pt reflect(const Pt& p) const
	{
		return p - n * 2 * 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;
}
// Checks if `p` is in the disk (the region in a plane
// bounded by a circle) of diameter [ab]
bool inDisk(const Pt& a, const Pt& b, const Pt& p)
{
	return sgn(dot(a - p, b - p)) <= 0;
}
// Checks if `p` lies on segment [ab]
bool onSegment(const Pt& a, const Pt& b, const Pt& p)
{
	return sgn(orient(a, b, p)) == 0 && inDisk(a, b, p);
}
// Checks if the segments [ab] and [cd] intersect
// properly (their intersection is one point
// which is not an endpoint of either segment)
bool properInter(const Pt& a, const Pt& b, const Pt& c, const Pt& d)
{
	db oa = orient(c, d, a);
	db ob = orient(c, d, b);
	db oc = orient(a, b, c);
	db od = orient(a, b, d);
	return sgn(oa) * sgn(ob) == -1 && sgn(oc) * sgn(od) == -1;
}
// Returns the distance between [ab] and `p`
db segPt(const Pt& a, const Pt& b, const Pt& p)
{
	Line l(a, b);
	assert(sgn(sq(l.n)) != 0);
	if (l.cmpProj(a, p) && l.cmpProj(p, b))
		return l.dist(p);
	return min(abs(p - a), abs(p - b));
}
// Returns the distance between [ab] and [cd]
db segSeg(const Pt& a, const Pt& b, const Pt& c, const Pt& d)
{
	if (properInter(a, b, c, d))
		return 0;
	return min({segPt(a, b, c), segPt(a, b, d),
			segPt(c, d, a), segPt(c, d, b)});
}
// Returns the circumcenter of triangle abc.
// The circumcircle of a triangle is a circle that passes through all three vertices.
Pt circumCenter(const Pt& a, Pt b, Pt c)
{
	b = b - a;
	c = c - a;
	assert(sgn(cross(b, c)) != 0);
	return a + perp(b * sq(c) - c * sq(b)) / cross(b, c) / 2;
}
// Returns circle-line intersection points
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};
}
// Returns circle-circle intersection points
vector<Pt> circleCircle(const Pt& o1, db r1, const Pt& o2, db r2)
{
	Pt d = o2 - o1;
	db d2 = sq(d);
	if (sgn(sqrt(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};
}

struct Sector
{
	Pt c;
	db r, s, theta;
	Line l[2];
	void read()
	{
		cin >> c.x >> c.y >> r >> s >> theta;
	}
	bool contains(const Pt& p) const
	{
		db d = abs(p - c);
		if (sgn(d) == 0)
			return true;
		if (sgn(d - r) > 0)
			return false;
		db phi = atan2(p.y - c.y, p.x - c.x);
		FOR(i, 0, 3)
		{
			if (sgn(s - phi) <= 0 && sgn(phi - (s + theta)) <= 0)
				return true;
			phi += 2 * PI;
		}
		return false;
	}
};

vector<Pt> getPtsOnSeg(const Pt& p1, const Pt& p2, const Sector& s)
{
	Line l(p1, p2);
	vector<Pt> res = {p1, p2};
	vector<Pt> qq = circleLine(s.c, s.r, l);
	qq.PB(s.c);
	FOR(i, 0, 2)
	{
		if (parallel(l, s.l[i]))
			continue;
		qq.PB(inter(l, s.l[i]));
	}
	for (const Pt& q : qq)
	{
		if (onSegment(p1, p2, q) && s.contains(q))
			res.PB(q);
	}
	sort(ALL(res), [&](const Pt& q1, const Pt& q2)
	{
		return sgn(abs(q1 - p1) - abs(q2 - p1)) < 0;
	});
	return res;
}

vector<db> getPhisOnArc(const Sector& s1, const Sector& s2)
{
	vector<Pt> qq = circleCircle(s1.c, s1.r, s2.c, s2.r);
	FOR(i, 0, 2)
	{
		vector<Pt> qqq = circleLine(s1.c, s1.r, s2.l[i]);
		qq.insert(qq.end(), ALL(qqq));
	}
	vector<db> res = {s1.s, s1.s + s1.theta};
	for (const Pt& q : qq)
	{
		if (!s1.contains(q) || !s2.contains(q))
			continue;
		db phi = atan2(q.y - s1.c.y, q.x - s1.c.x);
		while (sgn(s1.s - phi) > 0)
			phi += 2 * PI;
		assert(sgn(s1.s - phi) <= 0 && sgn(phi - (s1.s + s1.theta)) <= 0);
		res.PB(phi);
	}
	if (sgn(abs(s2.c - s1.c)) == 0 && sgn(s2.r - s1.r) == 0)
	{
		for (db phi : {s2.s - 2 * PI, s2.s + s2.theta - 2 * PI})
		{
			while (sgn(s1.s - phi) > 0)
				phi += 2 * PI;
			assert(sgn(s1.s - phi) <= 0);
			if (sgn(phi - (s1.s + s1.theta)) <= 0)
				res.PB(phi);
		}
	}
	sort(ALL(res));
	return res;
}

vector<pair<Pt, Pt>> getUsefulOnSeg(const Sector& s2, const vector<Pt>& v, int i, int j, const Pt& p)
{
	vector<pair<Pt, Pt>> res;
	FOR(k, 0, SZ(v) - 1)
	{
		Pt midPoint = (v[k] + v[k + 1]) / 2;
		if (!s2.contains(midPoint) || (j < i && onSegment(s2.c, p, midPoint)))
			res.PB({v[k], v[k + 1]});
	}
	return res;
}

vector<pair<db, db>> getUsefulOnArc(const Sector& s1, const Sector& s2, int i, int j)
{
	const auto& v = getPhisOnArc(s1, s2);
	vector<pair<db, db>> res;
	FOR(k, 0, SZ(v) - 1)
	{
		db phi = (v[k] + v[k + 1]) / 2;
		const Pt& p = {s1.c.x + s1.r * cos(phi), s1.c.y + s1.r * sin(phi)};
		if (!s2.contains(p) || (j < i && sgn(abs(s2.c - s1.c)) == 0 && sgn(s2.r - s1.r) == 0))
			res.PB({v[k], v[k + 1]});
	}
	return res;
}
int n;

void solve()
{
	vector<Sector> sectors(n);
	vector<vector<Pt>> p(n, vector<Pt>(2));
	FOR(i, 0, n)
	{
		Sector& sector = sectors[i];
		sector.read();
		FOR(j, 0, 2)
		{
			db phi = sector.s + j * sector.theta;
			p[i][j] = {sector.c.x + sector.r * cos(phi), sector.c.y + sector.r * sin(phi)};
			sector.l[j] = {sector.c, p[i][j]};
		}
	}
	db ans = 0;
	FOR(i, 0, n)
	{
		vector<pair<Pt, int>> eventsSeg[2] = {
			{{sectors[i].c, 1}, {p[i][0], -1}},
			{{sectors[i].c, 1}, {p[i][1], -1}}};
		vector<pair<db, int>> eventsArc = {{sectors[i].s, 1}, {sectors[i].s + sectors[i].theta, -1}};
		FOR(j, 0, n)
		{
			if (i == j)
				continue;
			FOR(ii, 0, 2)
			{
				auto ptsOnSeg = getPtsOnSeg(sectors[i].c, p[i][ii], sectors[j]);
				auto usefulOnSeg = getUsefulOnSeg(sectors[j], ptsOnSeg, i, j, p[j][ii]);
				for (const auto& [p1, p2] : usefulOnSeg)
				{
					eventsSeg[ii].PB({p1, 1});
					eventsSeg[ii].PB({p2, -1});
				}
			}
			auto usefulOnArc = getUsefulOnArc(sectors[i], sectors[j], i, j);
			for (auto [phi1, phi2] : usefulOnArc)
			{
				eventsArc.PB({phi1, 1});
				eventsArc.PB({phi2, -1});
			}
		}
		FOR(ii, 0, 2)
		{
			sort(ALL(eventsSeg[ii]), [&](const pair<Pt, int>& p1, const pair<Pt, int>& p2)
			{
				return sgn(abs(p1.F - sectors[i].c) - abs(p2.F - sectors[i].c)) < 0;
			});
			int bal = 0;
			db sum = 0;
			FOR(k, 0, SZ(eventsSeg[ii]))
			{
				bal += eventsSeg[ii][k].S;
				if (bal == n)
				{
					sum += cross(eventsSeg[ii][k].F, eventsSeg[ii][k + 1].F);
				}
			}
			ans += (ii == 0 ? 1 : -1) * sum;
		}
		sort(ALL(eventsArc));
		int bal = 0;
		FOR(k, 0, SZ(eventsArc))
		{
			bal += eventsArc[k].S;
			if (bal == n)
			{
				db phi1 = eventsArc[k].F, phi2 = eventsArc[k + 1].F;
				ans += sectors[i].r * (sectors[i].c.x * (sin(phi2) - sin(phi1))
					- sectors[i].c.y * (cos(phi2) - cos(phi1))
					+ sectors[i].r * (phi2 - phi1));
			}
		}
	}
	ans /= 2;
	cout << ans << "\n";
}

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


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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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.8005000000
1.1300000000
106.4449314387

result:

ok 3 numbers

Test #2:

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

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.9375000000
45.7125000000
43.5339208935
31.8020000000
41.8860000000
12.9320000000
31.7131023684
9.8900000000
3.8115000000
26.7900000000
37.1875000000
10.7005000000
31.4235000000
47.6640000000
25.4565000000
54.0135950929
47.2744417558
7.0325000000
10.0475000000
49.4407408607
12.5750972576
34.6755000...

result:

ok 250 numbers

Test #3:

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

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.1578797266
33.2350000000
47.7494614617
82.2800000000
38.5650000000
57.2875000000
16.8875000000
30.8124663241
18.2661373644
43.2646347552
42.4942175106
26.1327491758
26.4045000000
30.1067281147
48.9370000000
23.1395000000
56.7305000000
68.3693802649
56.9404374192
26.6910000000
36.5250853975
21.669...

result:

ok 166 numbers

Test #4:

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

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.0595920920
71.4725000000
72.3593375997
126.2555699205
53.3211949048
59.8770623786
47.6168767700
66.3827754345
26.7937631027
32.3415000000
139.8534669609
81.6631077735
102.7060531553
81.9198379646
30.2529013521
88.1009981263
102.5549210193
9.0996076152
44.6716546664
46.0261779359
78.3696050979
20....

result:

ok 125 numbers

Test #5:

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

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.6935851850
91.7368755903
79.4364704276
77.4532608997
98.2859865938
71.0892243407
7.7255000000
103.2766109011
18.8761113722
83.8517243211
37.1320955855
80.1442017837
100.6075000000
89.2278472713
94.9247284873
24.3560000000
48.9314468826
63.6808639542
99.0233123235
66.8077883434
79.8940642341
114.4...

result:

ok 100 numbers

Test #6:

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

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.4622557205
137.0804351577
68.2804406868
81.6749055444
161.3947250719
109.8547433057
88.8510980289
149.6638209557
141.2604538376
150.8285831537
103.5306254184
80.0421062642
135.5872223687
124.1546681573
142.2968212009
136.0738797386
149.1473128139
92.2250862106
183.2849699724
153.4337064187
95.69...

result:

ok 50 numbers

Test #7:

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

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.5724722000
423.4116570304
188.4935909619
663.6455975772
237.4745100299
435.6022632689
426.1323938292
393.5738057426
204.8775722582
211.3009743240
159.2460000000
84.7113142525
65.4090000000
288.2104292762
53.7875000000
323.6900728913
120.6720000000
39.8720000000
86.0760000000
281.1011776475
508.0...

result:

ok 97 numbers

Test #8:

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

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.4062643636
8029.7216025938
17841.1602425480
8905.3102780281
9364.4742997584
11342.7930630778
7432.2772632490
4958.0183094454
12178.8159549738
12163.5455088850
10152.0917877501
5644.2395557101
8047.1332784974
10406.1675437823
12195.3807592203
8933.7193932205
11099.2381531481
6810.7413616354
700...

result:

ok 50 numbers

Test #9:

score: 0
Accepted
time: 61ms
memory: 4368kb

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.8849722300
95856.6648952934
78262.9050292656
76227.5248539176
101278.1842571330
89979.8989753888
81706.6683813872

result:

ok 7 numbers

Test #10:

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

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.3949772387
4418.5085000000
33061.9534630507
45686.0564349662
12072.3394394762
5985.1840233855
50770.0015524606
42946.2058989874
20200.6037691547
36999.6579735946
4337.2160000000
5574.2805000000
35395.9132708220
24095.7051480671
48478.5594570858
28974.4279035247
3808.9000000000
32793.4135532898...

result:

ok 89 numbers

Test #11:

score: 0
Accepted
time: 28ms
memory: 4292kb

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.2831674432
21353.7227024780
17122.8576718631
17218.5077700685
20193.9549594570
18206.9337697565
16965.2172831176
19853.4329449543
18881.6198201280
12897.3844319026
17739.7295099854
20560.4009650299
21622.4733835713
21926.1067497684

result:

ok 14 numbers

Test #12:

score: 0
Accepted
time: 81ms
memory: 4276kb

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.6776297789
101085.3012157114
104860.5398828483
82685.0429512065
87897.3112154701

result:

ok 5 numbers

Test #13:

score: 0
Accepted
time: 502ms
memory: 4484kb

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

result:

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

Test #14:

score: 0
Accepted
time: 455ms
memory: 4448kb

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

result:

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

Test #15:

score: 0
Accepted
time: 448ms
memory: 4464kb

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

result:

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

Test #16:

score: 0
Accepted
time: 426ms
memory: 4376kb

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

result:

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

Test #17:

score: 0
Accepted
time: 421ms
memory: 4556kb

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

result:

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

Test #18:

score: 0
Accepted
time: 421ms
memory: 4456kb

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

result:

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

Test #19:

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

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.0250000000
26709.1664916088
6850.8797995131
26614.8461528655
11694.2169345109
11487.7440000000
327.1840000000
9187.7357676488
15880.6709436446
27506.6344681164
1788.1250000000
10038.2070000000
5846.0108242414
22964.3743202555
10425.3428053573
15011.3225000000
4879.4960000000
1531.8615000000
89...

result:

ok 167 numbers

Test #20:

score: 0
Accepted
time: 7ms
memory: 4260kb

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.5457417497
18615.9803879450
30226.6181854057
39138.6511190821
39292.9400771219
18460.2387477513
23656.3618976103
12845.7201427606
37815.5261487635
40040.1249813191
43511.6819659354
47180.7733132640
27510.0890724264
45552.1374095737
12807.6840392438
51146.1956047022
23595.4504345416
38727.65375...

result:

ok 68 numbers

Test #21:

score: 0
Accepted
time: 444ms
memory: 4508kb

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

result:

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

Test #22:

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

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.7236695970
26372.7705470885
72184.1194940198
47425.8535908970
51623.3994541974
33080.3379863001
32731.0716918096
45734.2183980164
43352.5205599143
57111.1455919893
67496.6961754943
28824.6905099922
52331.8993891173
42836.0308763754
36653.1703875863
69785.0452265991
49068.5150761705
55623.46236...

result:

ok 32 numbers

Extra Test:

score: 0
Extra Test Passed