Задача №112579. Спасти наш мир!
На одной из планет, под названием TheBestWorld, живут много умных людей. Эта планета также известна своими двумя конкурирующими школами супергероев. Каждый малыш, живущий на этой планете, мечтает стать супергероем, но не у всех это получается.
Ученики разных школ всегда недолюбливали друг друга. И иногда дело даже доходило до того, как супергерои начали применять свои геройские силы для выяснения отношений.
В этом мире случилось несчастье. На TheBestWorld нападают темные силы. У генерала главнокомандующего армией супергероев есть в распоряжении n + m супергероев, из них n — выпускники первой школы, m — второй. Главнокомандующий подсчитал количество супергероев k , которые смогут спасти лучшее, что у них есть, — планету.
На первый взгляд кажется, что главнокомандующему не понадобится помощь в выборе супергероев, но он вспомнил, что супергерои из разных школ раздражают друг друга. Но это происходит только тогда, когда два супергероя из разных школ находятся на расстоянии меньше d . Если такую пару героев позвать спасать мир, они не смогут продуктивно делать свою работу.
Проблема в том, что генерал забыл искомое d . Вам известны координаты каждого из супергероев. Генерал просит вас вычислить максимальное d , при котором он все еще может спасти мир. И выдать список супергероев, которые спасут мир при данном d .
В первой строке входного файла заданы три числа n , m и k ( 1 ≤ k , n , m ≤ n + m ≤ 200 ) — количество супергероев, выпустившихся из первой и второй школы, и количество супергероев, которое необходимо, чтобы спасти мир, соответственно. Следующие n + m строк описывают супергероев: в каждой строке заданы два целых числа — текущие координаты супергероя. Первые n строк содержат информацию о выпускниках первой школы, следующие m — о выпускниках второй школы. Все координаты не превышает по модулю 10000 . Известно, что никакие два супергероя не стоят в одной точке.
В первую строку выходного файла выведите одно вещественное число: максимальное значение d , которое позволяет спасти мир, либо -1, если при любом значении d мир можно спасти. Относительная или абсолютная погрешность вашего ответа не должна превышать 10 −6 . В следующих k строках выведите список номеров супергероев по одному числу в строке, которых можно взять при данном d , либо, если спасти мир можно при любом d , выведите список героев, которые позволяет спасти мир вне зависимости от d . Супергерои нумеруются числами от 1 до n + m в том порядке, в котором они идут во входном файле.
2 3 4 1 1 1 2 1 3 1 4 1 5
2.000000000000000000 1 3 4 5
1 1 2 1 1 1 10
9.000000000000000000 1 2