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

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

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

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

Условие

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

Считая Землю идеальным шаром, расстояние между двумя точками на поверхности можно вычислить по формуле
$arccos(sin(lat_1) \times sin(lat_2) + cos(lat_1) \times cos(lat_2) \times cos(lon_1-lon_2)) \times R$ ,
где $lon_1\,lat_1$ — долгота и широта первой точки, $lon_2\,lat_2$ — долгота и широта второй точки, $R = 6373 км$ — радиус Земли.

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

Во входном файле содержится число

$N$ , за которым следуют

$N$ пар целых чисел

$lon_i\,lat_i$ — долгота и широта

$i$ -го аэропорта в градусах.

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

В выходном файле должны содержаться

$N$ чисел

$r_i$ — расстояние в километрах от

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

Ограничения

$-180 \le lon_i \le 180$

$-90 \le lat_i \le 90$

$2 \le N \le 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`