This problem differs from Swiss Cheese Model (Hard) only in the Easy/Hard designation in the title and the red text. However, the Hard and Easy versions require different solution approaches. Solving the Hard version does not also solve the Easy version.
The Swiss cheese model is a model used in risk analysis. Even with multiple layers of protection, each layer has weaknesses. If these weaknesses happen to connect, a hazard can pass through all the layers and cause an accident.
You decide to study a simplified version of this model using several slices of cheese. Each slice is a flat slab of thickness that extends infinitely in the - and -directions. The slices are numbered from to , from front to back. The front face of slice lies in the plane , and its back face lies in the plane . Thus, the front and back faces of every slice are parallel to the -plane, and neighboring slices meet face to face with no gap.
Each slice has at least one cylindrical hole extending all the way from its front face to its back face. The axis of every hole is parallel to the -axis. Consequently, a cross-section of a hole parallel to the -plane is a disk with the same center coordinates and radius at every depth. All slices use the same coordinate system.
Represent the hazard as a moving point of zero size. Throughout its motion, it must remain inside a hole in some slice or on the boundary of a hole.
The hazard may change direction freely inside the holes. It can move between two holes in the same slice if their cross-sectional disks share at least one point. It can also move between neighboring slices if two holes share at least one point on the face where those slices meet. Moving back to an earlier slice is allowed.
The arrangement is unsafe if the hazard can travel from some hole on the front face of the first slice to some hole on the back face of the last slice.
Determine whether the given arrangement is safe, meaning that the hazard cannot pass all the way through.
The first line contains the number of slices .
The descriptions of slices through follow in order. The first line of the description of slice contains the number of holes in that slice. Each of the next lines contains three integers , , and , separated by spaces. They describe a hole whose cross-section parallel to the -plane is a disk with center and radius .
Print YES if the hazard cannot pass through all the slices, that is, if the arrangement is safe. Otherwise, print NO.
In the first example, the planar point belongs to a hole's cross-sectional disk in each of the three slices. Therefore, the hazard can pass through all the slices by moving parallel to the -axis from to , and the answer is NO.
In the third example, the two cross-sectional disks are tangent at the planar point . Traveling along hole boundaries is allowed, so the hazard can move from to . The answer is therefore .
In the fourth example, the hazard can move to the right through a sequence of holes within slice 2. Thus, it can pass all the way through even though the holes in slices 1 and 3 do not intersect directly. The answer is NO.
NO