
ZOJ Problem Set  3495
Dick likes building various designs by assembling his Lego blocks. Today he designed a new one that consisted of N bases and M long thin bricks on a horizon desktop. Each base was a circle and each brick must directly or indirectly stand on the bases. The design was perfect, except for he didn't know whether it could be built. So he asks you to help him answer this question. You are given the locations and the radiuses of the bases as well as the locations of the bricks in the form of the coordinates of the two endpoints of each brick. All the bases are stable and they can support arbitrary weight. The mass of each brick is equally distributed and it will be stable if it is placed on bases or stable bricks and the moment of it can be zero when it is placed. It will also keep stable after it is placed stably, for the bricks can be stuck to the base or other bricks below it if it is stable. Your task is to determine whether there is an order to place the bricks so that every brick is stable.
Input There are multiple test cases. The first line of input is an integer T ≈ 100 indicating the number of test cases. Each test case begins with two integers N and M (0 < N, M ≤ 100)  the number of bases and the number of bricks. N lines follow, each of which contains 3 integers x_{i}, y_{i} and r_{i}  the center and the radius of the ith base. Bases do not common point with each other. Then M lines follow, each of which contains 4 integers x1_{i}, y1_{i}, x2_{i} and y2_{i}  the coordinates of the two endpoints of the ith brick. The absolute value of each coordinate does not exceed 10000 and 0 < r_{i} ≤ 10000. Each brick will not degenerate. Output For each test case, output "YES" if the design can be built. Otherwise output "NO" instead. Sample Input 3 1 2 0 0 2 3 2 3 2 3 1 3 3 2 1 0 0 1 3 0 1 1 0 2 0 1 2 0 0 2 2 0 0 10 2 0 0 10 Sample Output YES YES NO Author: GUAN, Yao Contest: The 8th Zhejiang Provincial Collegiate Programming Contest 