[Home|Training|Problems|Contests|C Language] | [Login|Register] |
Problems Status Rank |
Problem 1282
Collision detection
Time Limit: 1000ms
Memory Limit: 65536kb Description
In movie The Terminator, the Terminator, a cyborg is sent back in time to assassinate Sarah Connor. In fact, there are n terminators in total. Due to the wrong record of destination, most of them got stuck in big rocks, and only the one looks like Arnold Schwarzenegger survived. Since the assassination has failed, the Skynet decides to sent n more Terminators. Given descriptions of all possible rocks, your task is to detect whether each Terminator would collide the rocks. To simplify the problem, the Terminator is regarded as a single point and each rock is described as a convex polyhedron. Input
The input contains only one test case. The first line consists of two integers n and m, which specify the number Terminators and rocks. (1 ≤ n,m ≤ 60) Next n lines each contains three integers (x,y,z), indicating the location of Terminators. The rest of input contains m blocks, which describe the m rocks. In each block, the first line contains two integers k and e, indicating the number of vertices and edges. (4 ≤ k ≤ 20, 6 ≤ e ≤ 60) Next k lines each contains three integers, indicating the location of vertices. The last e lines each describes an edge by two integers u and v. (1 ≤ u,v ≤ k, u ≠ v) All coordinates are non-negative and less than 1000. It is guaranteed that no two rocks intersect with each other. Output
Output should contain exactly n lines. Print “Terminator i: ” in the ith line, and then output “ready” if ith Terminator won’t get stuck in any rocks, or “oops” otherwise. Terminator would get stuck if he lies on the surface of a rock. Sample Input
6 1 0 0 0 1 1 0 0 0 10 3 4 5 6 5 5 6 6 6 8 12 1 1 1 1 1 6 1 6 1 1 6 6 6 1 1 6 1 6 6 6 1 6 6 6 1 2 3 4 5 6 7 8 1 3 1 5 3 7 5 7 2 4 2 6 4 8 6 8 Sample Output
Terminator 1: ready Terminator 2: ready Terminator 3: ready Terminator 4: oops Terminator 5: oops Terminator 6: oops |