ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Junior Contest October'2004

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Vladislava

Time limit: 1.0 second
Memory limit: 64 MB
— We call this satellite Vladya. As you know Vladislava has one more satellite, artificial as well, and also extra-terrestrial. It is smaller. We call it Slava, you get it? The planet is called Vladislava and it is natural to call its satellites Vladya and Slava, isn’t it?
— Yes, of course,— said Gorbovsky. He was familiar with this beautiful argumentation. He heard it for the third time. — You suggested it very wittily, August. Vladya and Slava — Vladislava. Splendid!
— You call these satellites respectively Y-one and Y-two on the Earth,— continued Bader,— Vladya and Slava. But we, we call them other way. We call them Vladya and Slava.
He looked at Valkenstein strictly. Valkenstein worked his jaws. As far as he knew “we” ment Bader himself and only Bader.
N artifacts of extra-terrestrial civilizations were found on the planet Vladislava.
The scientific spacecraft settled on the planet’s orbit and launched automatic probes, which found out that a storm-boat will be able to touch down only in one of M points on the planet’s surface because of the rough relief. Inasmuch as the transportation on the planet’s surface takes much time, it is reasonable to find the nearest landing place for each artifact.


The first line contains integers N and M (1 ≤ N, M ≤ 5000) — amounts of artifacts and landing grounds respectively. Then there is positive real R ≤ 1000 — that is the planet radius. Each of the following M lines consists of latitude Wi and longitude Li of one of the landing grounds, Wi, Li are real numbers, |Wi| ≤ 90, |Li| ≤ 180. The next N lines contain artifacts coordinates — latitude wi and longitude li — real numbers, |wi| ≤ 90, |li| ≤ 180. All real numbers are rounded to 6 digits after decimal point.


You are to output exactly N lines. ith line should contain the distance between the ith artifact and the nearest landing ground within two digits after a decimal point.


1 2
0 0
1 1
0 0
2 1
0 0
0 90
0 45
Problem Author: Alexander Bikbaev
Problem Source: The 10th Collegiate Programming Contest of the High School Pupils of the Sverdlovsk Region (October 16, 2004)
To submit the solution for this problem go to the Problem set: 1331. Vladislava