Весенний турнир 2007 - КрокодАвиа

Задача A. КрокодАвиа ≡

задачи
детали
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	И. Олейников	Ограничение времени:	1 сек
Входной файл:	input.txt	Ограничение памяти:	64 Мб
Выходной файл:	output.txt

Условие

Аэропорты авиакомпании "КрокодАвиа" расположены в N городах по всему земному шару. Авиакомпании требуется знать расстояние в километрах от каждого аэропорта до ближайшего из оставшихся.

Считая Землю идеальным шаром, расстояние между двумя точками на поверхности можно вычислить по формуле

arccos(sin(lat₁) × sin(lat₂) + cos(lat₁) × cos(lat₂) × cos(lon₁−lon₂)) × R,

где lon₁ lat₁ — долгота и широта первой точки, lon₂ lat₂ — долгота и широта второй точки, R = 6373км — радиус Земли.

Формат входного файла

Во входном файле содержится число N, за которым следуют N пар целых чисел lon_i lat_i — долгота и широта i-го аэропорта в градусах.

Формат выходного файла

В выходном файле должны содержаться N чисел r_i — расстояние в километрах от i-го аэропорта до ближайшего к нему. Расстояния должны быть указаны с точностью не менее трех знаков после запятой.

Ограничения

−180 ≤ lon_i ≤ 180

−90 ≤ lat_i ≤ 90

2 ≤ N ≤ 5000

Примеры тестов

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`2 0 0 180 0`	`20021.36998 20021.36998`
2	`3 -123 -12 -123 -12 0 0`	`0.000 0.000 13591.239`