QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#358131#3183. Blowing CandlesPetroTarnavskyi#AC ✓81ms13504kbC++202.3kb2024-03-19 17:30:472024-03-19 17:30:47

Judging History

This is the latest submission verdict.

  • [2024-03-19 17:30:47]
  • Judged
  • Verdict: AC
  • Time: 81ms
  • Memory: 13504kb
  • [2024-03-19 17:30:47]
  • Submitted

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'