|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|3 초||128 MB||0||0||0||0.000%|
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.
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.
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.
8 20 20 1 7 7 13 13 10 20 20 1 7 7 13 13 0 0 0 0
1.34 1.34 Smoking not permitted!