QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#358131 | #3183. Blowing Candles | PetroTarnavskyi# | AC ✓ | 81ms | 13504kb | C++20 | 2.3kb | 2024-03-19 17:30:47 | 2024-03-19 17:30:47 |
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 pair<int, int> PII;
typedef double db;
const db EPS = 1e-9;
struct Pt
{
db x, y;
Pt operator-(const Pt& p) const
{
return {x - p.x, y - p.y};
}
};
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 dist(const Pt& p) const
{
return abs(side(p)) / abs(n);
}
};
vector<Pt> convexHull(vector<Pt> v)
{
if (SZ(v) <= 1)
return v;
sort(ALL(v), [](const Pt& p, const Pt& q)
{
int dx = sgn(p.x - q.x);
if (dx != 0)
return dx < 0;
return sgn(p.y - q.y) < 0;
});
vector<Pt> lower, upper;
for (const Pt& p : v)
{
while (SZ(lower) > 1
&& sgn(orient(lower[SZ(lower) - 2],
lower.back(), p)) <= 0)
lower.pop_back();
while (SZ(upper) > 1
&& sgn(orient(upper[SZ(upper) - 2],
upper.back(), p)) >= 0)
upper.pop_back();
lower.PB(p);
upper.PB(p);
}
reverse(ALL(upper));
lower.insert(lower.end(), next(upper.begin()),
prev(upper.end()));
return lower;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
int n, r;
cin >> n >> r;
vector<Pt> v(n);
for (Pt& p : v)
cin >> p.x >> p.y;
v = convexHull(v);
n = SZ(v);
int ptr = 0;
db ans = 47.0 * r;
FOR(i, 0, n)
{
ptr = max(ptr, i + 1);
Line l(v[i], v[(i + 1) % n]);
while (sgn(l.dist(v[(ptr + 1) % n]) - l.dist(v[ptr % n])) > 0)
{
ptr++;
}
ans = min(ans, l.dist(v[ptr % n]));
}
cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3904kb
input:
3 10 0 0 10 0 0 10
output:
7.071067811865476
result:
ok found '7.07107', expected '7.07107', error '0.00000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
4 100 0 0 2 2 1 1 1 5
output:
1.568929081105472
result:
ok found '1.56893', expected '1.56893', error '0.00000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
4 100 0 0 -2 2 -1 1 -5 1
output:
1.568929081105472
result:
ok found '1.56893', expected '1.56893', error '0.00000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 4028kb
input:
4 100 0 0 -2 -2 -1 -1 -1 -5
output:
1.568929081105472
result:
ok found '1.56893', expected '1.56893', error '0.00000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
4 100 0 0 2 -2 1 -1 5 -1
output:
1.568929081105472
result:
ok found '1.56893', expected '1.56893', error '0.00000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
4 100 0 0 2 -2 1 -1 1 -5
output:
1.568929081105472
result:
ok found '1.56893', expected '1.56893', error '0.00000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4032kb
input:
4 100 0 0 2 2 1 1 5 1
output:
1.568929081105472
result:
ok found '1.56893', expected '1.56893', error '0.00000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
4 100 0 0 -2 2 -1 1 -1 5
output:
1.568929081105472
result:
ok found '1.56893', expected '1.56893', error '0.00000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
4 100 0 0 -2 -2 -1 -1 -5 -1
output:
1.568929081105472
result:
ok found '1.56893', expected '1.56893', error '0.00000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
3 20 10 0 10 1 10 2
output:
0.000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
3 20 10 0 10 2 10 1
output:
0.000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
3 20 10 1 10 0 10 2
output:
0.000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
3 20 10 1 10 2 10 0
output:
0.000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 4036kb
input:
3 20 10 2 10 0 10 1
output:
0.000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
3 20 10 2 10 1 10 0
output:
0.000000000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
4 100 1 1 1 2 2 1 2 2
output:
1.000000000000000
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #17:
score: 0
Accepted
time: 48ms
memory: 13504kb
input:
159642 10000001 0 -10000000 0 10000000 9999999 4472 -9999999 -4472 9999999 -4472 -9999999 4472 9999998 6325 -9999998 -6325 9999998 -6325 -9999998 6325 9999997 7746 -9999997 -7746 9999997 -7746 -9999997 7746 9999996 8944 -9999996 -8944 9999996 -8944 -9999996 8944 9999995 10000 -9999995 -10000 9999995...
output:
19999998.000000000000000
result:
ok found '19999998.00000', expected '19999998.00000', error '0.00000'
Test #18:
score: 0
Accepted
time: 77ms
memory: 9472kb
input:
200000 200000000 -44688205 41976403 -33839845 29990058 -31711709 11730345 47374949 -87301387 88366817 84095012 18719148 -9530672 21317633 -5557360 -73266917 -5960533 -27326101 19621387 86286450 17667444 63943748 98704956 86174018 24493783 59901906 -25187148 35104828 -10000233 93129026 63144824 -5652...
output:
199994149.062393963336945
result:
ok found '199994149.06239', expected '199994149.06239', error '0.00000'
Test #19:
score: 0
Accepted
time: 79ms
memory: 9576kb
input:
200000 200000000 -21722245 47249047 3745652 18507096 25288815 11982590 -70315255 -62453490 -70300814 -16869663 84335219 -82689738 -42406547 -88845871 -75147195 -69168189 -72109075 41293273 -63826547 -62603953 16241675 77805523 59364926 22486411 19338940 -27908233 91240467 6899258 -97814572 34690208 ...
output:
199997471.623106032609940
result:
ok found '199997471.62311', expected '199997471.62311', error '0.00000'
Test #20:
score: 0
Accepted
time: 79ms
memory: 9432kb
input:
200000 200000000 95049215 30688972 -45277904 22437968 -73293137 33923272 30223549 54244476 25199933 87238859 49062903 -41383484 -87731675 76744319 90637696 37076366 -8871363 81411906 -6591136 -30519973 34063981 -38995939 63153676 22816043 67667151 98817206 -61667198 90130567 -58409293 23156835 -5614...
output:
199997197.126268297433853
result:
ok found '199997197.12627', expected '199997197.12627', error '0.00000'
Test #21:
score: 0
Accepted
time: 75ms
memory: 9460kb
input:
200000 200000000 -5731582 -25614801 -29580993 -67063995 -13729701 -45474895 39422127 -57302146 33062038 41691433 -97744986 1472243 -63278879 -43354258 6493471 -21835147 44663767 62678874 32167994 93865049 -92006486 25647031 -79600488 -70967485 51050213 -68615014 -50958616 36896692 42753963 16752922 ...
output:
199995772.838815450668335
result:
ok found '199995772.83882', expected '199995772.83882', error '0.00000'
Test #22:
score: 0
Accepted
time: 79ms
memory: 9552kb
input:
200000 200000000 -68427956 -66643590 50290435 67146136 90455718 94955610 72881956 4099369 91338021 39474232 -58068198 -59351775 30557841 -96987494 85884434 65624924 35236518 -77940367 13494835 -98383373 57639571 28148087 -84355557 16928766 11865908 -8593835 -50594003 -17973658 -29956039 -70062037 -4...
output:
199997226.194480478763580
result:
ok found '199997226.19448', expected '199997226.19448', error '0.00000'
Test #23:
score: 0
Accepted
time: 81ms
memory: 9420kb
input:
200000 200000000 -60435657 -36857470 -9357928 82707300 -31307662 -25591697 -59037919 -40252597 33693631 18082719 -71506737 30432033 -23857680 -17265964 -14539340 -19320466 17269792 -34055941 17000726 -58064093 17008359 -5293956 3008341 -39882600 -9171619 -74408808 -89524827 -31848255 63231912 -90769...
output:
199998606.672401070594788
result:
ok found '199998606.67240', expected '199998606.67240', error '0.00000'