This problem differs from Swiss Cheese Model (Easy) 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 line up, 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 path of the hazard must be a straight line perpendicular to the front and back faces of the slices. In other words, it must move parallel to the -axis, and every point on its path must have the same planar coordinates .
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, several holes are connected within slice 2, but no straight line passes through holes in every slice. Thus, the arrangement is safe, and the answer is YES.
NO