Welcome to ZOJ
Select Problem
ZOJ Problem Set - 1472
Overlapping Shapes

Time Limit: 2 Seconds      Memory Limit: 65536 KB

There are problems easy to human brain, but hard to computers. For example, a man can tell whether two shapes overlap by a single glimpse, but a computer will have to check this and that before giving a correct answer.

In this problem, you are asked to write a program that checks whether two shapes overlap. Two shapes are said to overlap if and only if the two shapes touch on at least one point. Notice that the case in which one shape lies completely inside the other shape is NOT considered as "overlap". For simplicity, only two special kinds of shapes are taken into account: circle and rectangle.


The first line of input contains an integer n which is the number of tests. Each test consists of two lines, specifying the characteristics of the two shapes. A shape specification begins with a string which is either "circle" or "rectangle". If it is a circle, then three integers follow: r, x, and y where x and y are the coordinates of the center of the circle and r is the radius. Otherwise four integers follow: x1, y1, x2, and y2, specifying the coordinates of the top-left corner and the right-bottom corner. All the coordinates will be within the range [-50000, 50000], and 0 < r < 50000.


For each test, if the two shapes overlap, print "yes" in a single line; otherwise print "no".

Sample Input

circle 1 0 0
circle 2 0 0
rectangle 0 10 10 0
rectangle 0 20 20 0
circle 10 0 0
rectangle 100 200 200 100

Sample Output


Author: CHEN, Shunbao
Source: ZOJ Monthly, December 2002
Submit    Status