| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 16 | 14 | 12 | 100.000% |
И вновь в Семи Королевствах проблемы! До Роберта Баратеона --- короля государства --- дошли слухи о появлении драконов. Он хочет как можно скорее оповестить об опасности все $n$ городов, расположенных на территории государства. К несчастью, Джоффри --- сын короля --- перестрелял из рогатки почти всех почтовых голубей. Остался всего один. Теперь король хочет выбрать город, чтобы послать из него гонца, который оповестит все оставшиеся города, затратив на это минимальное время.
Но гонцы в Семи Королевствах чрезвычайно ленивые, они не утруждаются составлением маршрута обхода городов. Однако они придерживаются определенной стратегии:
Пускай гонец находится в городе $i$. И до этого он посетил множество городов $M$. Тогда следующим он посетит город $j,ドル ближайший к городу $i,ドル и при этом не принадлежащий множеству $M$. Если таких городов несколько, он посетит город с минимальным номером.
Города представлены как точки на плоскости с координатами $x_i, y_i$ в декартовой системе координат. Расстояние и время, затрачиваемое гонцами на передвижение между городами, определяется как квадрат евклидового расстояния между точками, которые соответствуют городам.
Помогите Роберту Баратеону выбрать город, гонец из которого посетит все остальные города за минимальное время.
В первой строке входного файла дано число $n$ --- число городов (2ドル \le n \le 300$).
В следующих $n$ строках дано описание городов --- координаты $x_i, y_i$ ($-300 \le x_i, y_i \le 300$).
В единственной строке выходного файла выведите минимальное время, за которое все города могут быть оповещены.
7 2 4 4 3 7 2 7 5 9 7 5 8 2 7
51