Техасские Лета
Лето в Техасе может быть очень жарким. Однако техасцы стойкие, и в каком-то странном смысле некоторые из них даже наслаждаются этой жарой; ведь в Техасе всё больше, даже жара. Тем не менее, такая погода может быть довольно некомфортной для студентов факультета компьютерных наук, которые недавно приехали в Техас и не привыкли к потоотделению, которое она вызывает.
Эти студенты хотят минимизировать количество пота, которое они выделяют, идя от общежития до класса. Когда они выходят на солнце, они начинают потеть. Чем дольше они остаются на солнце, тем больше они потеют. Количество пота пропорционально квадрату времени, в течение которого они непрерывно находятся на солнце. Иными словами, если они находятся на солнце непрерывно в течение s секунд, они будут потеть C_s^2 галлонов, где C — это постоянная, которая различается у разных студентов. Но если они находят тенистое место по пути, их непрерывное пребывание на солнце прерывается, и они сразу же перестают потеть. Они могут сесть в тени и полностью остыть, прежде чем продолжить путь в класс. Конечно, выход из тени означает, что они снова начинают потеть.
Напишите программу, которая поможет студенту найти путь от общежития до класса, минимизируя общее количество пота, которое он выделяет.
Входные данные
Входные данные описывают расположение тенистых мест на кампусе, а также местоположение общежития и класса студента. Входные данные начинаются с строки, содержащей целое число 0 ≤ n ≤ 2500, количество тенистых мест. Каждая из следующих n строк содержит пару целых чисел x y, указывающих координаты тенистого места. Ни у двух тенистых мест нет одинаковых координат. После тенистых мест следуют еще две строки в том же формате, которые указывают координаты общежития и класса студента соответственно.
Выходные данные
Выведите путь, по которому студент может пройти от общежития до класса. Путь должен минимизировать общее количество пота, выделяемого на всем пути. Выведите путь в виде индексов тенистых мест (в порядке, указанном во входных данных, при этом первое тенистое место имеет индекс 0). Если лучший путь не содержит тенистых мест, выведите один символ '-'. Если существует несколько путей, минимизирующих общее количество пота, выведите любой из них.