CandyOnDisk
SRM 571 · 2012-12-13 · by cgy4ever
SRM 571 · 2012-12-13 · by cgy4ever · Geometry, Graph Theory
Problem Statement
Problem Statement
Fox Ciel is playing the "DJ Box" set of levels in the "Cut the Rope" game on her smartphone.
In the current level, she is facing the following problem:
The level can be seen as a two-dimensional plane that contains a single candy and some disks. You are given the description of the level:int[] s x, y, and r; and int s sx, sy, tx, and ty.
Theint[] s x, y, and r describe the disks:
For each i, there is a disk centered at (x[i], y[i]) with radius r[i].
Some of the disks may overlap.
The candy is initially located at (sx, sy), and the goal of the game is to move it to (tx, ty).
The game is played by rotating some of the disks, one after another. More precisely, in each step, Ciel may choose any disk that currently contains the candy, and rotate the disk by any desired angle around its center. The candy rotates with the chosen disk. Other disks are ignored during the rotation. (If the candy is located exactly on the border of a disk, we still consider it to be on the disk.)
Return "YES" if she can solve the level in finitely many steps, and "NO" otherwise.
The level can be seen as a two-dimensional plane that contains a single candy and some disks. You are given the description of the level:
The
The game is played by rotating some of the disks, one after another. More precisely, in each step, Ciel may choose any disk that currently contains the candy, and rotate the disk by any desired angle around its center. The candy rotates with the chosen disk. Other disks are ignored during the rotation. (If the candy is located exactly on the border of a disk, we still consider it to be on the disk.)
Return "YES" if she can solve the level in finitely many steps, and "NO" otherwise.
Constraints
- x will contain between 1 and 50 elements, inclusive.
- x, y, and r will each contain the same number of elements.
- Each element in x, y will be between -1,000,000,000 and 1,000,000,000, inclusive.
- Each element in r will be between 1 and 1,000,000,000, inclusive.
- sx, sy, tx and ty will be between -1,000,000,000 and 1,000,000,000, inclusive.
- The answer will not change if we increase the radii of all disks by 1e-3. Neither will it change if we decrease the radii of all disks by 1e-3.
Examples
0)
{0, 4}
{0, 0}
{3, 3}
-1
-2
6
1
Returns: "YES"
You have two disks. You can win the level by first rotating the yellow disk to move the candy from S to A = (2,1), and then rotating the green disk to move the candy from A to T.
1)
{0, 3}
{0, 0}
{5, 3}
-4
0
-2
0
Returns: "YES"
This time you need 3 steps: S->A->B->T.
2)
{0}
{0}
{1}
0
0
571
571
Returns: "NO"
The target point is outside of the only disk, so we clearly cannot reach it.
3)
{0}
{0}
{1}
571
571
571
571
Returns: "YES"
4)
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
{2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2}
2
2
19
19
Returns: "YES"
Submissions are judged against all 98 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CandyOnDisk with a public method string ableToAchieve(vector<int> x, vector<int> y, vector<int> r, int sx, int sy, int tx, int ty) · 98 test cases · 2 s / 256 MB per case