QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#562558 | #182. Cover the Polygon with Your Disk | PetroTarnavskyi# | AC ✓ | 268ms | 4304kb | C++20 | 5.3kb | 2024-09-13 18:39:46 | 2024-09-13 18:39:46 |
Judging History
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;
template<typename T>
void updMin(T& a, T b)
{
a = min(a, b);
}
template<typename T>
void updMax(T& a, T b)
{
a = max(a, b);
}
const db EPS = 1e-9;
const db PI = acos(-1.0);
const db INF = 1e9;
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);
}
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 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);
}
bool inConvexPolygon(const vector<Pt>& v, const Pt& a)
{
assert(SZ(v) >= 3);
if (sgn(orient(v.back(), v[0], a)) < 0
|| sgn(orient(v[0], v[1], a)) < 0)
return false;
int i = lower_bound(v.begin() + 2, v.end(), a,
[&](const Pt& p, const Pt& q)
{
return sgn(orient(v[0], p, q)) > 0;
}) - v.begin();
return sgn(orient(v[i - 1], v[i], a)) >= 0;
}
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};
}
int n;
db r;
vector<Pt> v;
vector<Line> lines;
db area(const Pt& o)
{
vector<db> angles = {0};
db res = 0;
FOR(i, 0, n)
{
const Pt& p1 = v[i];
const Pt& p2 = v[(i + 1) % n];
vector<Pt> points = {p1, p2};
vector<Pt> inter = circleLine(o, r, lines[i]);
for (const Pt& q : inter)
{
if (onSegment(p1, p2, q))
{
points.PB(q);
angles.PB(atan2(q.y - o.y, q.x - o.x));
}
}
sort(ALL(points), [&](const Pt& q1, const Pt& q2)
{
return sgn(abs(q1 - p1) - abs(q2 - p1)) < 0;
});
FOR(j, 0, SZ(points) - 1)
{
const Pt& q1 = points[j];
const Pt& q2 = points[j + 1];
const Pt& qm = (q1 + q2) / 2;
if (sgn(abs(qm - o) - r) < 0)
{
res += cross(q1, q2);
}
}
}
sort(ALL(angles));
angles.PB(angles[0] + 2 * PI);
FOR(i, 0, SZ(angles) - 1)
{
db phi1 = angles[i], phi2 = angles[i + 1], phim = (phi1 + phi2) / 2;
const Pt& qm = {o.x + r * cos(phim), o.y + r * sin(phim)};
if (inConvexPolygon(v, qm))
{
res += r * (r * (phi2 - phi1)
+ o.x * (sin(phi2) - sin(phi1))
- o.y * (cos(phi2) - cos(phi1)));
}
}
return res;
}
db xMin = INF, xMax = -INF, yMin = INF, yMax = -INF;
db solve(db x, db le, db ri)
{
FOR(i, 0, 74)
{
db m1 = le + (ri - le) / 3, m2 = ri - (ri - le) / 3;
if (area({x, m1}) < area({x, m2}))
le = m1;
else
ri = m2;
}
return area({x, (le + ri) / 2});
}
db solve(db x)
{
db yMid = -47;
FOR(i, 0, n)
{
const Pt& p = v[i];
const Pt& q = v[(i + 1) % n];
db xLeft = min(p.x, q.x);
db xRight = max(p.x, q.x);
if (sgn(xLeft - x) <= 0 && sgn(x - xRight) <= 0)
{
if (sgn(q.x - p.x) == 0)
yMid = p.y;
else
yMid = (q.y - p.y) * (x - p.x) / (q.x - p.x) + p.y;
}
}
assert(sgn(yMin - yMid) <= 0 && sgn(yMid - yMax) <= 0);
db le = yMin, ri = yMid;
FOR(i, 0, 74)
{
db m = (le + ri) / 2;
if (sgn(area({x, m})) > 0)
ri = m;
else
le = m;
}
db res = solve(x, (le + ri) / 2, yMid);
le = yMid, ri = yMax;
FOR(i, 0, 74)
{
db m = (le + ri) / 2;
if (sgn(area({x, m})) > 0)
le = m;
else
ri = m;
}
updMax(res, solve(x, yMid, (le + ri) / 2));
return res;
}
db solve()
{
for (const Pt& p : v)
{
updMin(xMin, p.x);
updMax(xMax, p.x);
updMin(yMin, p.y);
updMax(yMax, p.y);
}
db le = xMin, ri = xMax;
FOR(i, 0, 74)
{
db m1 = le + (ri - le) / 3, m2 = ri - (ri - le) / 3;
if (solve(m1) < solve(m2))
le = m1;
else
ri = m2;
}
return solve((le + ri) / 2);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(6);
cin >> n >> r;
v.resize(n);
for (Pt& p : v)
cin >> p.x >> p.y;
FOR(i, 0, n)
lines.PB({v[i], v[(i + 1) % n]});
cout << solve() / 2 << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 144ms
memory: 4204kb
input:
4 4 0 0 6 0 6 6 0 6
output:
35.759506
result:
ok found '35.75951', expected '35.75951', error '0.00000'
Test #2:
score: 0
Accepted
time: 119ms
memory: 4260kb
input:
3 1 0 0 2 1 1 3
output:
2.113100
result:
ok found '2.11310', expected '2.11310', error '0.00000'
Test #3:
score: 0
Accepted
time: 151ms
memory: 4288kb
input:
3 1 1 1 3 1 1 3
output:
1.809571
result:
ok found '1.80957', expected '1.80957', error '0.00000'
Test #4:
score: 0
Accepted
time: 125ms
memory: 4236kb
input:
3 1 0 0 100 1 99 1
output:
0.019799
result:
ok found '0.01980', expected '0.01980', error '0.00000'
Test #5:
score: 0
Accepted
time: 113ms
memory: 4288kb
input:
3 1 0 0 50 49 100 100
output:
1.375406
result:
ok found '1.37541', expected '1.37541', error '0.00000'
Test #6:
score: 0
Accepted
time: 110ms
memory: 4248kb
input:
4 10 50 0 55 50 50 100 45 50
output:
175.478767
result:
ok found '175.47877', expected '175.47877', error '0.00000'
Test #7:
score: 0
Accepted
time: 111ms
memory: 4232kb
input:
4 10 50 0 55 75 50 100 45 30
output:
135.978901
result:
ok found '135.97890', expected '135.97890', error '0.00000'
Test #8:
score: 0
Accepted
time: 111ms
memory: 4284kb
input:
4 1 0 0 100 10 100 12 0 1
output:
3.137569
result:
ok found '3.13757', expected '3.13757', error '0.00000'
Test #9:
score: 0
Accepted
time: 119ms
memory: 4240kb
input:
3 10 0 0 32 0 13 28
output:
303.035987
result:
ok found '303.03599', expected '303.03599', error '0.00000'
Test #10:
score: 0
Accepted
time: 186ms
memory: 4168kb
input:
6 10 10 0 20 0 26 9 20 18 10 18 4 9
output:
284.045176
result:
ok found '284.04518', expected '284.04518', error '0.00000'
Test #11:
score: 0
Accepted
time: 72ms
memory: 4240kb
input:
3 1 0 0 20 0 10 20
output:
3.141593
result:
ok found '3.14159', expected '3.14159', error '0.00000'
Test #12:
score: 0
Accepted
time: 75ms
memory: 4280kb
input:
3 2 0 0 2 0 1 2
output:
2.000000
result:
ok found '2.00000', expected '2.00000', error '0.00000'
Test #13:
score: 0
Accepted
time: 116ms
memory: 4224kb
input:
4 1 0 0 2 0 2 2 0 2
output:
3.141593
result:
ok found '3.14159', expected '3.14159', error '0.00000'
Test #14:
score: 0
Accepted
time: 108ms
memory: 4212kb
input:
4 20 20 0 40 20 20 40 0 20
output:
800.000000
result:
ok found '800.00000', expected '800.00000', error '0.00000'
Test #15:
score: 0
Accepted
time: 94ms
memory: 4284kb
input:
4 1 0 0 100 0 100 2 0 2
output:
3.141593
result:
ok found '3.14159', expected '3.14159', error '0.00000'
Test #16:
score: 0
Accepted
time: 93ms
memory: 4268kb
input:
4 1 0 0 2 0 2 100 0 100
output:
3.141593
result:
ok found '3.14159', expected '3.14159', error '0.00000'
Test #17:
score: 0
Accepted
time: 152ms
memory: 4236kb
input:
10 10 0 0 10 0 20 1 30 3 40 6 50 10 60 15 70 21 80 28 90 36
output:
177.728188
result:
ok found '177.72819', expected '177.72819', error '0.00000'
Test #18:
score: 0
Accepted
time: 78ms
memory: 4168kb
input:
4 72 0 0 100 0 100 100 0 100
output:
10000.000000
result:
ok found '10000.00000', expected '10000.00000', error '0.00000'
Test #19:
score: 0
Accepted
time: 268ms
memory: 4284kb
input:
10 49 50 0 79 10 96 32 96 68 79 90 50 100 21 90 4 68 4 32 21 10
output:
7181.603297
result:
ok found '7181.60330', expected '7181.60330', error '0.00000'
Test #20:
score: 0
Accepted
time: 105ms
memory: 4188kb
input:
10 45 50 0 79 10 96 32 96 68 79 90 50 100 21 90 4 68 4 32 21 10
output:
6361.725124
result:
ok found '6361.72512', expected '6361.72512', error '0.00000'
Test #21:
score: 0
Accepted
time: 111ms
memory: 4264kb
input:
10 52 50 0 79 10 96 32 96 68 79 90 50 100 21 90 4 68 4 32 21 10
output:
7192.000000
result:
ok found '7192.00000', expected '7192.00000', error '0.00000'
Test #22:
score: 0
Accepted
time: 157ms
memory: 4224kb
input:
10 21 1 29 10 33 35 45 53 55 63 61 75 72 54 67 47 65 15 52 2 43
output:
575.597046
result:
ok found '575.59705', expected '575.59705', error '0.00000'
Test #23:
score: 0
Accepted
time: 153ms
memory: 4236kb
input:
10 28 13 63 15 31 38 32 67 37 90 42 95 56 94 65 92 68 40 87 28 78
output:
2333.534182
result:
ok found '2333.53418', expected '2333.53418', error '0.00000'
Test #24:
score: 0
Accepted
time: 183ms
memory: 4304kb
input:
10 32 17 29 33 1 68 13 69 14 81 30 76 53 71 63 41 82 24 51 18 38
output:
3043.754463
result:
ok found '3043.75446', expected '3043.75446', error '0.00000'
Test #25:
score: 0
Accepted
time: 156ms
memory: 4248kb
input:
10 32 10 45 12 36 42 10 51 11 60 17 74 34 74 87 68 89 51 78 17 52
output:
2754.863700
result:
ok found '2754.86370', expected '2754.86370', error '0.00000'
Test #26:
score: 0
Accepted
time: 148ms
memory: 4200kb
input:
10 30 21 10 33 6 82 12 81 42 80 46 72 67 40 79 31 72 29 69 24 60
output:
2804.426966
result:
ok found '2804.42697', expected '2804.42697', error '0.00000'
Test #27:
score: 0
Accepted
time: 124ms
memory: 4184kb
input:
4 11 32 32 54 12 52 56 44 94
output:
365.562027
result:
ok found '365.56203', expected '365.56203', error '0.00000'
Test #28:
score: 0
Accepted
time: 128ms
memory: 4196kb
input:
4 44 0 59 81 7 89 52 50 100
output:
3894.212831
result:
ok found '3894.21283', expected '3894.21283', error '0.00000'
Test #29:
score: 0
Accepted
time: 143ms
memory: 4236kb
input:
4 33 17 75 67 27 98 9 61 42
output:
353.029999
result:
ok found '353.03000', expected '353.03000', error '0.00000'
Test #30:
score: 0
Accepted
time: 111ms
memory: 4204kb
input:
5 33 7 67 67 27 98 9 61 42 17 75
output:
681.196424
result:
ok found '681.19642', expected '681.19642', error '0.00000'
Test #31:
score: 0
Accepted
time: 112ms
memory: 4300kb
input:
5 11 7 32 71 10 85 11 85 26 78 30
output:
365.376768
result:
ok found '365.37677', expected '365.37677', error '0.00000'
Test #32:
score: 0
Accepted
time: 142ms
memory: 4180kb
input:
5 41 13 48 21 13 96 8 41 98 28 76
output:
3653.925918
result:
ok found '3653.92592', expected '3653.92592', error '0.00000'
Test #33:
score: 0
Accepted
time: 118ms
memory: 4284kb
input:
5 27 17 78 21 46 87 61 99 65 91 100
output:
1759.664252
result:
ok found '1759.66425', expected '1759.66425', error '0.00000'
Test #34:
score: 0
Accepted
time: 115ms
memory: 4264kb
input:
5 17 22 21 26 0 79 5 94 35 63 29
output:
776.922068
result:
ok found '776.92207', expected '776.92207', error '0.00000'
Test #35:
score: 0
Accepted
time: 137ms
memory: 4188kb
input:
5 23 36 1 72 28 96 48 78 45 47 25
output:
501.886896
result:
ok found '501.88690', expected '501.88690', error '0.00000'
Test #36:
score: 0
Accepted
time: 129ms
memory: 4232kb
input:
6 21 7 32 71 10 85 11 85 26 78 30 21 52
output:
907.269057
result:
ok found '907.26906', expected '907.26906', error '0.00000'
Test #37:
score: 0
Accepted
time: 123ms
memory: 4304kb
input:
6 27 14 63 21 46 87 61 99 65 91 100 17 78
output:
1759.664252
result:
ok found '1759.66425', expected '1759.66425', error '0.00000'
Test #38:
score: 0
Accepted
time: 145ms
memory: 4260kb
input:
6 23 36 1 72 28 96 48 78 45 58 40 47 25
output:
624.386896
result:
ok found '624.38690', expected '624.38690', error '0.00000'
Test #39:
score: 0
Accepted
time: 147ms
memory: 4204kb
input:
7 30 15 74 16 67 33 52 88 13 96 25 73 56 59 70
output:
1476.848306
result:
ok found '1476.84831', expected '1476.84831', error '0.00000'
Test #40:
score: 0
Accepted
time: 141ms
memory: 4236kb
input:
7 29 0 19 51 78 58 97 41 92 33 82 27 72 11 42
output:
760.704608
result:
ok found '760.70461', expected '760.70461', error '0.00000'
Test #41:
score: 0
Accepted
time: 152ms
memory: 4208kb
input:
7 27 3 34 16 36 59 63 63 67 52 89 23 73 11 58
output:
1329.017909
result:
ok found '1329.01791', expected '1329.01791', error '0.00000'
Test #42:
score: 0
Accepted
time: 146ms
memory: 4192kb
input:
7 32 27 64 35 40 45 17 53 0 92 2 82 39 49 56
output:
2068.205435
result:
ok found '2068.20543', expected '2068.20544', error '0.00000'
Test #43:
score: 0
Accepted
time: 141ms
memory: 4204kb
input:
7 17 4 75 22 48 29 47 78 50 95 53 43 72 4 81
output:
795.735342
result:
ok found '795.73534', expected '795.73534', error '0.00000'
Test #44:
score: 0
Accepted
time: 146ms
memory: 4228kb
input:
8 29 0 19 51 78 58 97 52 100 41 92 33 82 27 72 11 42
output:
773.727185
result:
ok found '773.72718', expected '773.72719', error '0.00000'
Test #45:
score: 0
Accepted
time: 139ms
memory: 4188kb
input:
8 33 7 31 45 17 67 14 70 27 73 45 68 97 63 99 16 83
output:
3329.116714
result:
ok found '3329.11671', expected '3329.11671', error '0.00000'
Test #46:
score: 0
Accepted
time: 135ms
memory: 4248kb
input:
8 15 49 44 58 25 62 19 82 15 88 15 91 41 81 45 80 45
output:
693.381393
result:
ok found '693.38139', expected '693.38139', error '0.00000'
Test #47:
score: 0
Accepted
time: 140ms
memory: 4180kb
input:
8 30 21 10 33 6 82 12 81 42 80 46 72 67 40 79 29 69
output:
2751.873656
result:
ok found '2751.87366', expected '2751.87366', error '0.00000'
Test #48:
score: 0
Accepted
time: 164ms
memory: 4200kb
input:
8 27 2 51 17 18 70 30 98 38 61 61 51 65 26 72 9 59
output:
2139.814045
result:
ok found '2139.81405', expected '2139.81405', error '0.00000'
Test #49:
score: 0
Accepted
time: 207ms
memory: 4224kb
input:
9 40 0 44 3 38 28 21 50 16 93 33 76 76 43 96 8 90 2 63
output:
4776.568951
result:
ok found '4776.56895', expected '4776.56895', error '0.00000'
Test #50:
score: 0
Accepted
time: 153ms
memory: 4212kb
input:
9 21 1 29 10 33 35 45 53 55 63 61 75 72 54 67 15 52 2 43
output:
569.595726
result:
ok found '569.59573', expected '569.59573', error '0.00000'
Test #51:
score: 0
Accepted
time: 170ms
memory: 4204kb
input:
9 29 0 19 22 9 51 78 58 97 52 100 41 92 33 82 27 72 11 42
output:
1264.901476
result:
ok found '1264.90148', expected '1264.90148', error '0.00000'
Test #52:
score: 0
Accepted
time: 155ms
memory: 4192kb
input:
9 15 49 44 58 25 62 19 82 15 88 15 96 20 91 41 81 45 80 45
output:
699.525932
result:
ok found '699.52593', expected '699.52593', error '0.00000'
Test #53:
score: 0
Accepted
time: 145ms
memory: 4220kb
input:
9 30 21 10 33 6 82 12 81 42 80 46 72 67 40 79 31 72 29 69
output:
2751.873656
result:
ok found '2751.87366', expected '2751.87366', error '0.00000'
Test #54:
score: 0
Accepted
time: 150ms
memory: 4244kb
input:
9 14 2 30 5 28 38 9 45 5 61 4 72 9 28 25 9 31 3 32
output:
314.764305
result:
ok found '314.76430', expected '314.76430', error '0.00000'