Czech ACM Student Chapter

Czech Technical University in Prague

acm

Charles University in Prague

Technical University of Ostrava

cz

Slovak University of Technology

Masaryk University

ˇ

ˇ ´

University of Zilina

Pavol Jozef Safarik University in Koˇice

s

CTU Open Contest 2010

Prohibici´n de fumar

o

fumar.c, fumar.C, fumar.java, fumar.p

When travelling abroad (to the World Finals, for example), you should always obey all local laws

of every country you visit. In some countries, they have laws that prohibit smoking closer than

some given distance D from any building. In a modern world, it becomes a pressing question

whether there is any place where you could legally smoke in a town at all.∗

Fortunately, the town we consider here was built in an orderly way, making it easier to decide

this question. The boundary of the town is an axis-parallel rectangle R and the buildings are

pairwise disjoint axis-parallel rectangles contained inside R. Since police patrols are generally

not equipped with micrometers, it is possible to smoke at any spot within the town (including

the boundary rectangle) whose distance to the closest building is at least (D - 1) meters and 90

centimeters.

Input Specification

The input contains several towns. Each town description consists of several lines. The first line

contains four integers D, Rx, Ry , and N separated by a space. The number D (1 ≤ D ≤ 100 000)

gives the minimum distance from the buildings at which the smoking is legal. Rx and Ry

(1 ≤ Rx, Ry ≤ 100 000) give the dimensions of the town, which covers a rectangle with vertices

at the coordinates (0, 0), (Rx, 0), (Rx, Ry ), and (0, Ry ). Finally, N (0 ≤ N ≤ 200) is the number

of buildings in the town.

Each of the following N lines contains four integers Fx, Fy , Tx, Ty (0 ≤ Fx < Tx ≤ Rx,

0 ≤ Fy < Ty ≤ Ry ), giving the coordinates (Fx, Fy ), (Fx, Ty ), (Tx, Ty ), and (Tx, Fy ) of the

corners of the particular buildings.

The last town is followed by a line containing four zeros.

Output Specification

For each input instance, if there is any place in the town where smoking is permitted, output

a single line containing two real numbers X and Y rounded to two decimal places, giving the

coordinates (X, Y ) of any point inside the town boundaries whose distance is at least D -

0.1m from any of the buildings. Otherwise, the line should contain the string "Smoking not

permitted!".

To avoid rounding errors, you may assume that the town is built in such a way that either there

exists a point whose distance from every building is at least D + 0.1m, or that all points in the

town are closer than D - 0.1m to some building.

∗

Or, from the other perspective, whether your favorite town finally became smoke-free.

Sample Input

8 20 20 1

7 7 13 13

10 20 20 1

7 7 13 13

0000

Output for Sample Input

1.34 1.34

Smoking not permitted!