TopCoder SRM 571 - 1000: CandyOnDisk

Problem Statement

在二维平面上有 N 个圆，圆心为(x_i,y_i)，半径为r_i。
给出起点(sx,sy)和终点(tx,ty)，
求在有限次行动内是否可以从起点走到终点。

每次行动，可以选择一个圆，要求当前点被这个圆包含。
然后将这个圆旋转任意角度，而这个点会随着这个圆同步旋转。

范围：N <= 50,
-10^9 <= x_i,y_i,r_i,sx,sy,tx,ty <= 10^9。

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 vector<int> , vector<int> , vector<int> , int , int , int , int
Returns string
Method signature string ableToAchieve(vector<int> x, vector<int> y, vector<int> r, int sx, int sy, int tx, int ty)

(be sure your method is public)

Limits

Time limit (s) 2.000
Memory limit (MB) 64

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.

Test cases

input
- x { 0, 4 }
- y { 0, 0 }
- r { 3, 3 }
- sx -1
- sy -2
- tx 6
- ty 1
output
Returns "YES"

note

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.
input
- x { 0, 3 }
- y { 0, 0 }
- r { 5, 3 }
- sx -4
- sy 0
- tx -2
- ty 0
output
Returns "YES"

note

This time you need 3 steps: S->A->B->T.
input
- x { 0 }
- y { 0 }
- r { 1 }
- sx 0
- sy 0
- tx 571
- ty 571
output
Returns "NO"

note

The target point is outside of the only disk, so we clearly cannot reach it.
input
- x { 0 }
- y { 0 }
- r { 1 }
- sx 571
- sy 571
- tx 571
- ty 571
output
Returns "YES"
input
- x { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }
- y { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }
- r { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }
- sx 2
- sy 2
- tx 19
- ty 19
output
Returns "YES"
input
- x { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }
- y { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }
- r { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
- sx 2
- sy 2
- tx 19
- ty 19
output
Returns "NO"

back to the menu

SRM 571 1 1000 CandyOnDisk

Problem Statement

Definition

Limits

Constraints

Test cases