e-olymp
Məsələlər

Кухонный робот

Кухонный робот

Роботы со временем становятся все популярнее. Сегодня их используют не только на больших заводах, но и в домашних условиях. Один программист вместе со своими друзьями решили создать своего собственного домашнего робота. Как Вы знаете, большинство программистов любит собираться на вечеринки и пить пиво. После ее завершения на столе остается множество пустых бутылок. Поэтому было решено создать робота, который будет способен собрать пустые бутылки со стола.

Стол представляет собой прямоугольник с длиной l и шириной w. Робот стартует с точки (xr, yr) и n бутылок находится в точках (xi, yi) (1in). Для того чтобы забрать бутылку, робот должен переместиться в точку где она расположена и взять ее, после чего отнести бутылку в некоторую точку на границе стола и отпустить ее. В любой момент времени робот может держать только одну бутылку, а отпускать ее только на границе стола.

prb2268

Размеры бутылок и робота считайте пренебрежимо малыми (робот и бутылки являются точками). Роботу, держащему бутылку, можно передвигаться через точку, в которой находится другая бутылка.

Одной из подпрограмм робота является планирование маршрута. Вам следует написать программу, которая найдет маршрут минимальной длины, по которому робот соберет все бутылки.

Входные данные

Первая строка содержит два целых числа w и l (2w, l1000) - ширина и длина стола.

Вторая строка содержит количество бутылок на столе n (1n18). Каждая из следующих n строк содержит два целых числа xi и yi - координаты i-ой бутылки (0 < xi < w, 0 < yi < l). Никакие две бутылки не располагаются в одной точке.

Последняя строка входных данных содержит два целых числа xr и yr - координаты начального положения робота (0 < xr < w, 0 < yr < l). Робот не находится в одной точке ни с какой бутылкой.

Выходные данные

Вывести длину кратчайшего пути, по которому робот соберет все бутылки. Ошибка точности вычислений не должна превышать 10-6.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
3 4
2
1 1
2 3
2 1
Çıxış verilənləri #1
5.60555127546399
Müəllif Fedor Tsarev
Mənbə 2010 ACM NEERC, Northern Subregion, October 30, Problem K