CandyOnDisk | Topcoder Archive

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 ints sx, sy, tx, and ty.

The int[]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.

Definition

Class:: CandyOnDisk
Method:: ableToAchieve
Parameters:: int[], int[], int[], int, int, int, int
Returns:: String
Method signature:: String ableToAchieve(int[] x, int[] y, int[] r, int sx, int sy, int tx, int ty)
(be sure your method is public)

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, 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.
```
{0, 3}
```
```
{0, 0}
```
```
{5, 3}
```
```
-4
```
```
0
```
```
-2
```
```
0
```
```
Returns: "YES"
```
This time you need 3 steps: S->A->B->T.
```
{0}
```
```
{0}
```
```
{1}
```
```
0
```
```
0
```
```
571
```
```
571
```
```
Returns: "NO"
```
The target point is outside of the only disk, so we clearly cannot reach it.
```
{0}
```
```
{0}
```
```
{1}
```
```
571
```
```
571
```
```
571
```
```
571
```
```
Returns: "YES"
```

{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}

Returns: "YES"

{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}

{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

Returns: "NO"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.