QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#534278#7310. Circular SectorsmshcherbaWA 9ms4320kbC++2010.0kb2024-08-26 23:25:402024-08-26 23:25:40

Judging History

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

  • [2024-08-26 23:25:40]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:4320kb
  • [2024-08-26 23:25:40]
  • 提交

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)
	{
		#warning
		// assuming the circles don't coincide
		cerr << d2 << endl;
		assert(sgn(r2 - r1) != 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};
}

mt19937 rng;

int rand(int a, int b)
{
	return a + rng() % (b - a);
}

void perturb(Pt& p)
{
	const int C = 1e6;
	p.x += 1e-8 * rand(-C, C + 1) / C;
	p.y += 1e-8 * rand(-C, C + 1) / C;
}

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);
	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);
	}
	sort(ALL(res));
	return res;
}

vector<pair<Pt, Pt>> getUsefulOnSeg(const Sector& s2, const vector<Pt>& v)
{
	vector<pair<Pt, Pt>> res;
	FOR(i, 0, SZ(v) - 1)
	{
		if (!s2.contains((v[i] + v[i + 1]) / 2))
			res.PB({v[i], v[i + 1]});
	}
	return res;
}

vector<pair<db, db>> getUsefulOnArc(const Sector& s1, const Sector& s2)
{
	const auto& v = getPhisOnArc(s1, s2);
	vector<pair<db, db>> res;
	FOR(i, 0, SZ(v) - 1)
	{
		db phi = (v[i] + v[i + 1]) / 2;
		const Pt& p = {s1.c.x + s1.r * cos(phi), s1.c.y + s1.r * sin(phi)};
		if (!s2.contains(p))
			res.PB({v[i], v[i + 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();
		perturb(sector.c);
		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);
				for (const auto& [p1, p2] : usefulOnSeg)
				{
					eventsSeg[ii].PB({p1, 1});
					eventsSeg[ii].PB({p2, -1});
				}
			}
			auto usefulOnArc = getUsefulOnArc(sectors[i], sectors[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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

result:

ok 3 numbers

Test #2:

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

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.5339209128
31.8020000000
41.8860000000
12.9320000000
31.7131023705
9.8900000000
3.8115000000
26.7900000000
37.1875000000
10.7005000035
31.4235000000
47.6640000000
25.4565000000
54.0135950822
47.2744417629
7.0325000000
10.0475000000
49.4407408731
12.5750972567
34.6755000...

result:

ok 250 numbers

Test #3:

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

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.1578797486
33.2350000000
47.7494614476
82.2800000000
38.5650000000
57.2875000000
16.8875000000
30.8124663184
18.2661373709
43.2646347616
42.4942175211
26.1327491637
26.4045000000
30.1067281133
48.9370000000
23.1395000000
56.7305000000
68.3693801517
56.9404374083
26.6910000000
36.5250853849
21.669...

result:

ok 166 numbers

Test #4:

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

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.0595921216
71.4725000000
72.3593375998
126.2555698604
53.3211949039
59.8770623446
47.6168767838
66.3827754289
26.7937630789
32.3415000000
139.8534669002
81.6631077387
102.7060531202
81.9198379530
30.2529013266
88.1009981521
102.5549210932
9.0996076136
44.6716546958
46.0261779576
78.3696050285
20....

result:

ok 125 numbers

Test #5:

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

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.6935851751
91.7368755682
79.4364704320
77.4532609166
98.2859865867
71.0892243108
7.7255000000
103.2766108978
18.8761113717
83.8517243070
37.1320955728
80.1442018858
100.6075000000
89.2278472871
94.9247284126
24.3560000000
48.9314468494
63.6808639748
99.0233124012
66.8077884000
79.8940642727
114.4...

result:

ok 100 numbers

Test #6:

score: -100
Wrong Answer
time: 9ms
memory: 4308kb

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.4622557720
137.0804351275
68.2804406589
81.6749055254
161.3947250258
109.8547433732
88.8510980287
149.6638209412
141.2604538005
150.8285832209
103.5306253863
80.0421062943
135.5872223624
124.1546681585
142.2968212704
136.0738797792
149.1473126537
92.2250861713
183.2849698307
153.4337064555
95.69...

result:

wrong answer 24th numbers differ - expected: '162.2110536', found: '162.0052576', error = '0.0012687'