| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
На одной из планет, под названием TheBestWorld, живут много умных людей. Эта планета также известна своими двумя конкурирующими школами супергероев. Каждый малыш живущий на этой планете мечтает стать супергероем, но не у всех это получается.
Ученики разных школ всегда недолюбливали друг друга. И иногда дело даже доходило до того, как супергерои начали применять свои геройские силы для выяснения отношений.
В этом мире случилось несчастье. На TheBestWorld нападают темные силы. У генерала главнокомандующего армией супергероев есть в распоряжении $n + m$ супергероев, из них $n$ --- выпускники первой школы, $m$ --- второй. Главнокомандующий подсчитал количество супергероев $k,ドル которые смогут спасти лучшее, что у них есть, --- планету.
На первый взгляд кажется, что главнокомандующему не понадобится помощь в выборе супергероев, но он вспомнил, что супергерои из разных школ раздражают друг друга. Но это происходит только тогда, когда два супергероя из разных школ находятся на расстоянии меньше $d$. Если такую пару героев позвать спасать мир, они не смогут продуктивно делать свою работу.
Проблема в том, что генерал забыл искомое $d$. Вам известны координаты каждого из супергероев. Генерал просит вас вычислить максимальное $d,ドル при котором он все еще может спасти мир. И выдать список супергероев, которые спасут мир при данном $d$.
В первой строке входного файла заданы три числа $n,ドル $m$ и $k$ (1ドル \le k,\ n,\ m \le n + m \le 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.0 1 3 4 5
1 1 2 1 1 1 10
9.0 1 2