QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#346007#3195. Within Arm's ReachPetroTarnavskyi#AC ✓1ms4040kbC++202.8kb2024-03-07 19:33:272024-03-07 19:33:30

Judging History

This is the latest submission verdict.

  • [2024-03-07 19:33:30]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 4040kb
  • [2024-03-07 19:33:27]
  • 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 long 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};
	}
	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};
}

vector<Pt> circleCircle(const Pt& o1, db r1,
	const Pt& o2, db r2)
{
	Pt d = o2 - o1;
	db d2 = sq(d);
	if (sgn(d2) == 0)
	{
		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};
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(15);
	int n;
	cin >> n;
	VI l(n), sufSum(n), sufMx(n), rMin(n);
	for (int& li : l)
		cin >> li;
	Pt target;
	cin >> target.x >> target.y;
	sufSum[n - 1] = l[n - 1];
	sufMx[n - 1] = l[n - 1];
	RFOR(i, n - 1, 0)
	{
		sufSum[i] = sufSum[i + 1] + l[i];
		sufMx[i] = max(sufMx[i + 1], l[i]);
	}
	FOR(i, 0, n)
	{
		rMin[i] = max(0, 2 * sufMx[i] - sufSum[i]);
	}
	db absTarget = abs(target);
	if (sgn(absTarget - rMin[0]) < 0)
	{
		if (sgn(absTarget) == 0)
			target = {(db)rMin[0], 0};
		else
			target = target * (rMin[0] / absTarget);
	}
	else if (sgn(absTarget - sufSum[0]) > 0)
		target = target * (sufSum[0] / absTarget);
	Pt p = {0, 0};
	vector<Pt> ans;
	FOR(i, 0, n - 1)
	{
		Pt q = {p.x + l[i], p.y};
		db dist = abs(target - q);
		// rMin[i + 1] <= dist && dist <= sufSum[i + 1]
		if (sgn(rMin[i + 1] - dist) <= 0 && sgn(dist - sufSum[i + 1]) <= 0)
		{
			p = q;
		}
		else
		{
			vector<Pt> vec;
			vec = circleCircle(p, l[i], target, sufSum[i + 1]);
			if (!vec.empty())
				p = vec[0];
			else
			{
				assert(rMin[i + 1] != 0);
				vec = circleCircle(p, l[i], target, rMin[i + 1]);
				assert(!vec.empty());
				p = vec[0];
			}
		}
		ans.PB(p);
	}
	ans.PB(target);
	for (const Pt& q : ans)
		cout << q.x << " " << q.y << "\n";
	assert(sgn(abs(ans[0]) - l[0]) == 0);
	FOR(i, 0, n - 1)
		assert(sgn(abs(ans[i + 1] - ans[i]) - l[i + 1]) == 0);
	return 0;
	
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3928kb

input:

2
4
2
-8 -3

output:

-3.745316710276178 -1.404493766353567
-5.617975065414267 -2.106740649530350

result:

ok ACCEPTED

Test #2:

score: 0
Accepted
time: 1ms
memory: 4040kb

input:

1
10
10 0

output:

10.000000000000000 0.000000000000000

result:

ok ACCEPTED

Test #3:

score: 0
Accepted
time: 1ms
memory: 3872kb

input:

1
10
0 0

output:

10.000000000000000 0.000000000000000

result:

ok ACCEPTED

Test #4:

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

input:

2
10
5
2 2

output:

7.071067811865475 7.071067811865475
3.535533905932738 3.535533905932738

result:

ok ACCEPTED

Test #5:

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

input:

3
100
20
20
80 90

output:

86.311321218928029 50.501047805397308
83.155660609464014 70.250523902698654
80.000000000000000 90.000000000000000

result:

ok ACCEPTED

Test #6:

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

input:

3
5
10
4
5 3

output:

4.055075586697438 -2.925125977829063
5.629949608868375 6.950083985219375
5.000000000000000 3.000000000000000

result:

ok ACCEPTED

Test #7:

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

input:

3
3
3
3
-1 -1

output:

3.000000000000000 0.000000000000000
0.471405860129076 1.614376559483697
-1.000000000000000 -1.000000000000000

result:

ok ACCEPTED

Test #8:

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

input:

11
31
1
62
125
250
500
2
7
3
1000
15
-2 -3

output:

17.195706082982103 25.793559124473154
17.750406279207332 26.625609418810998
52.141818445171537 78.212727667757306
121.479342973325178 182.219014459987767
260.154392029632458 390.231588044448687
537.504490142247019 806.256735213370529
538.613890534697478 807.920835802046216
542.496791908274081 813.74...

result:

ok ACCEPTED

Test #9:

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

input:

3
5
3
4
5 3

output:

5.000000000000000 0.000000000000000
7.981423969999720 0.333333333333333
5.000000000000000 3.000000000000000

result:

ok ACCEPTED

Test #10:

score: 0
Accepted
time: 1ms
memory: 3868kb

input:

20
3
9
15
5
7
13
4
17
8
999
16
6
10
14
2
12
1000
11
998
1
234 -123

output:

3.000000000000000 0.000000000000000
12.000000000000000 0.000000000000000
27.000000000000000 0.000000000000000
32.000000000000000 0.000000000000000
39.000000000000000 0.000000000000000
52.000000000000000 0.000000000000000
56.000000000000000 0.000000000000000
73.000000000000000 0.000000000000000
81.00...

result:

ok ACCEPTED

Test #11:

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

input:

20
11
857
509
877
13
811
991
997
937
853
787
739
919
7
859
941
929
773
947
863
9871 -7919

output:

11.000000000000000 0.000000000000000
868.000000000000000 0.000000000000000
1377.000000000000000 0.000000000000000
2254.000000000000000 0.000000000000000
2267.000000000000000 0.000000000000000
3078.000000000000000 0.000000000000000
4069.000000000000000 0.000000000000000
5066.000000000000000 0.0000000...

result:

ok ACCEPTED

Test #12:

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

input:

20
919
625
820
609
760
41
101
232
545
812
234
177
678
131
359
444
519
77
173
917
0 0

output:

919.000000000000000 0.000000000000000
1544.000000000000000 0.000000000000000
2364.000000000000000 0.000000000000000
2973.000000000000000 0.000000000000000
3733.000000000000000 0.000000000000000
3774.000000000000000 0.000000000000000
3875.000000000000000 0.000000000000000
4107.000000000000000 0.00000...

result:

ok ACCEPTED

Test #13:

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

input:

20
919
625
820
609
760
41
101
232
545
812
234
177
678
131
359
444
519
77
173
917
0 -20000

output:

0.000000000000000 -919.000000000000000
0.000000000000000 -1544.000000000000000
0.000000000000000 -2364.000000000000000
0.000000000000000 -2973.000000000000000
0.000000000000000 -3733.000000000000000
0.000000000000000 -3774.000000000000000
0.000000000000000 -3875.000000000000000
0.000000000000000 -41...

result:

ok ACCEPTED

Test #14:

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

input:

20
408
663
148
685
731
606
538
289
850
577
732
34
656
200
325
901
105
575
754
910
-2498 1075

output:

408.000000000000000 0.000000000000000
1071.000000000000000 0.000000000000000
1219.000000000000000 0.000000000000000
1904.000000000000000 0.000000000000000
2635.000000000000000 0.000000000000000
3241.000000000000000 0.000000000000000
3779.000000000000000 0.000000000000000
4049.180270340308621 102.584...

result:

ok ACCEPTED

Test #15:

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

input:

20
440
377
296
985
425
377
777
533
710
620
975
854
312
130
13
900
745
416
550
507
-1080 -2184

output:

440.000000000000000 0.000000000000000
817.000000000000000 0.000000000000000
1113.000000000000000 0.000000000000000
2098.000000000000000 0.000000000000000
2523.000000000000000 0.000000000000000
2900.000000000000000 0.000000000000000
3677.000000000000000 0.000000000000000
4210.000000000000000 0.000000...

result:

ok ACCEPTED

Test #16:

score: 0
Accepted
time: 1ms
memory: 3864kb

input:

4
890
306
65
120
-10 14

output:

-517.301992409995799 724.222789373994119
-339.443105131952300 475.220347184733220
-301.662622540211033 422.327671556295447
-231.914039293919465 324.679655011487251

result:

ok ACCEPTED

Test #17:

score: 0
Accepted
time: 1ms
memory: 3960kb

input:

20
149
380
248
401
43
631
977
207
511
496
14
425
179
867
9
801
432
766
684
358
-3887 7982

output:

-65.234837156882222 133.960501720152790
-231.605562791883862 475.604734295039101
-340.184352153674405 698.572549238649114
-515.749249468505083 1059.097120982147562
-534.575410527202637 1097.756863089305750
-810.838378621113255 1665.066101917603807
-1238.586270582683260 2543.451405143035189
-1329.214...

result:

ok ACCEPTED

Test #18:

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

input:

20
121
803
712
959
971
452
892
694
465
489
201
20
757
995
643
853
797
755
203
452
2501 643

output:

121.000000000000000 0.000000000000000
924.000000000000000 0.000000000000000
1636.000000000000000 0.000000000000000
2595.000000000000000 0.000000000000000
3566.000000000000000 0.000000000000000
4018.000000000000000 0.000000000000000
4910.000000000000000 0.000000000000000
5604.000000000000000 0.000000...

result:

ok ACCEPTED

Test #19:

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

input:

20
397
740
397
939
260
942
166
856
939
700
98
740
470
621
506
843
433
261
951
662
10019 -4091

output:

397.000000000000000 0.000000000000000
1137.000000000000000 0.000000000000000
1534.000000000000000 0.000000000000000
2473.000000000000000 0.000000000000000
2733.000000000000000 0.000000000000000
3675.000000000000000 0.000000000000000
3841.000000000000000 0.000000000000000
4697.000000000000000 0.00000...

result:

ok ACCEPTED

Test #20:

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

input:

6
870
915
808
598
10
881
-4251 -946

output:

-849.226298514601961 -188.983316489017515
-1742.378095228235058 -387.741632106777315
-2531.084818446394120 -563.257172018416570
-3114.805883402407882 -693.156049329258494
-3124.567105224414801 -695.328271357867890
-3984.530747743224373 -886.701032078355741

result:

ok ACCEPTED

Test #21:

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

input:

1
500
-40 80

output:

-223.606797749978970 447.213595499957939

result:

ok ACCEPTED