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.
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 xi, yi and ri - the center and the radius of the i-th base. Bases do not common point with each other. Then M lines follow, each of which contains 4 integers x1i, y1i, x2i and y2i - the coordinates of the two endpoints of the i-th brick. The absolute value of each coordinate does not exceed 10000 and 0 < ri ≤ 10000. Each brick will not degenerate.
For each test case, output "YES" if the design can be built. Otherwise output "NO" instead.
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
YES YES NO
Author: GUAN, Yao
Contest: The 8th Zhejiang Provincial Collegiate Programming Contest