Ограничение памяти: 64 М байт

Cinoc is a mountain region that offers a spectacular natural environment. The area is sometimes called the last wilderness area, but in reality the Cinoc Mountains area is a cultural landscape. The mountains of Cinoc are also an important recreational area for people from around the world and have a particular characteristic: all of them have conic form (a right cone with circular base) and are placed on a completely flat land.

In order to attend any possible emergency, the administration of the Cinoc National Park requires to install two towers of communication, to connect two distant places in the park. The connection between the towers is only possible if there is a line of sight between the two towers, that is to say, the highest point of one tower can be seen from the highest point of the other tower. Also, to avoid interferences, the distance from any point in the line of sight to any point on the territory must be greater than zero.

Your task is to write a program that, given a map of the park and the description of the two towers, decides if the connection is possible or not.

Input

The first line of the input contains an integer number k (0 ≤ k ≤ 50), and is followed by k + 2 lines. The number k is the number of mountains in Cinoc Mountains region. Each of the next k lines contains four positive, integer numbers xm, ym, hm and rm (0 ≤ xm, ym, hm, rm ≤ 10000), describing a conic mountain. xm, ym, hm denotes the coordinates of the top of the mountain and rm denotes the radius of the base. The last two lines contain the information, associated with the towers: three numbers per line: xt, yt and ht (0 ≤ xt, yt, ht ≤ 10000). xt, yt, ht denotes the location of the tower’s top.

Output

If there exist a valid line of sight between the corresponding top points of the towers, the following line must be printed: “Yes”. In other case, the following line must be printed: “No”.

Sample Input and Output

Задача 4. Diamond Dealer

Input File: diamond.in

Output File: diamond.out

Time Limit: 1 second

Memory Limit: 64M byte

Mr. Chou is the flatworld diamond dealer. It is important that he knows the value of his (two dimensional) diamonds in order to be a successful businessman. Mr. Chou is tired of calculating the values by hand and you have to write a program that makes the calculation for him. The value of a diamond is determined by smoothness of its surface. This depends on the amount of faces on the surface, more faces means a smoother surface. If there are dents in the surface of the diamond, the value of the diamond decreases.

Counting the number of dents in the surface (a) and the number of faces on the surface that are not in dents (b), the value of the diamond is determined by the following formula: v = - a · p + b · q. When v is negative, the diamond has no value (i.e. zero value).

Input

The first line of input containing:

— The cost for a dent in the surface of a diamond (0 ≤ p ≤ 100);

— The value of a face in the surface of a diamond (0 ≤ q ≤ 100);

— The number of vertices (3 ≤ n ≤ 30) used to describe the shape of the diamond.

Than n lines containing one pair of integers (-1000 ≤ x_i, y_i ≤ 1000) describing the surface of the diamond (x₀, y₀) - (x₁, y₁) - ... - (x_n-1, y_n-1) - (x₀, y₀) in clockwise order.

No combination of three vertices within one diamond will be linearly aligned.

Output

The output contains one line with one number: the value of the diamond.

Поиск по сайту: