eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Spotlight Movement

Spotlight Movement

Ciel, an idol whose appearance and behavior are similar to a fox, is participating in a rehearsal for the live concert which takes place in a few days. To become a top idol, a large amount of effort is required! The live stage can be expressed as a two-dimensional surface. The live stage has \textbf{N} spotlights to illuminate the stage. The \textbf{i}-th spotlight casts a light in the range of a circle with radius \textbf{r_i}. The center of the light cast by the \textbf{i}-th spotlight moves along an orbital path \textbf{R_i}. \textbf{R_i} is described as a closed polygon, though \textbf{R_i} might contain self-intersections. The spotlight begins to move from the first vertex of \textbf{R_i}. All of the orbital period of each spotlight are the same. Each spotlight moves at a constant speed, and all of them return to the starting point at the same time. In the rehearsal, Ciel has to move from the starting point to the ending point indicated on the live stage. To achieve her goal, it is not allowed to fall out from the area illuminated with the spotlight. But, she doesn't have to be illuminated with the spotlight as long as she is standing on the starting point. You may assume that she can move fast enough. Answer if it is possible for her to move to the ending point. \InputFile Each input dataset is given in the following format: \textbf{N s_x s_y e_x e_y} \textbf{r_1 K_1 x_11 y_11 x_12 y_12 ... x_1K1 y_1K1} \textbf{r_2 K_2 x_21 y_21 x_22 y_22 ... x_2K2 y_2K2} \textbf{...} \textbf{r_N K_N x_N1 y_N1 x_N2 y_N2 ... x_NKN y_NKN} All inputs are integer. All coordinate information satisfies \textbf{−10000} ≤ \textbf{x}, \textbf{y} ≤ \textbf{10000}. \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{100}) indicates the number of spotlights. \textbf{(s_x, s_y)} and \textbf{(e_x, e_y)} indicate the starting point and the ending point of Ciel’s path, respectively. The following \textbf{N} lines denote the information of each spotlight. \textbf{r_i} (\textbf{1} ≤ \textbf{r_i} ≤ \textbf{100}) indicates the radius of the spotlight. \textbf{K_i} (\textbf{2} ≤ \textbf{K_i} ≤ \textbf{10}) indicates the number of vertices in the orbital path. Then, \textbf{K_i} vertices are given. Two consecutive vertices on the same orbital path are located at different places. The spotlight moves from the first point \textbf{(x_i1, y_i1)} to the second point \textbf{(x_i2, y_i2)}, then moves to the third point \textbf{(x_i3, y_i3)}, and so on. After moving to the \textbf{K_i}-th point \textbf{(x_iKi, y_iKi)}, the spotlight returns to the first point \textbf{(x_i1, y_i1)} and repeats again its movement. Let \textbf{d_ij} be the closest distance between two central points of spotlight \textbf{i} and spotlight \textbf{j}. \textbf{d_ij} satisfies either of the following: \begin{itemize} \item \textbf{d_ij} > \textbf{r_i+r_j+0.000001} \item \textbf{d_ij} < \textbf{r_i+r_j−0.000001} \end{itemize} Furthermore, let di be the closest distance between a central point of spotlight i and either the starting point or the ending point. \textbf{d_i} satisfies either of the following: \begin{itemize} \item \textbf{d_i} > \textbf{r_i+0.000001} \item \textbf{d_i} < \textbf{r_i−0.000001} \end{itemize} \OutputFile If it is possible for Ciel to move the ending point without falling out from the illuminated area, output \textbf{Yes} in one line. Otherwise, output \textbf{No}.
Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB
Вхідні дані #1
2 1 1 9 -1
2 2 1 1 -9 1
1 2 -1 -1 9 -1
Вихідні дані #1
Yes
Джерело Japan Alumni Group Summer Camp 2013 Day 4, 2013/09/23