| ENG RUS | Timus Online Judge |
USU Junior Contest October'2004
Contest is over
E. VladislavaTime 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. InputThe 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. OutputYou 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. Samples
Problem Author: Alexander Bikbaev Problem Source: The 10th Collegiate Programming Contest of the High School Pupils of the Sverdlovsk Region (October 16, 2004) |