Юпитерианские ювелиры
Планета Юпитер славится своими искусными ювелирами. Самыми ценными во всей Солнечной системе считаются плоские украшения, представляющие собой набор бриллиантов, соединённые перемычками из золота. Перемычка - это прямой кусок проволоки, соединяющий два драгоценных камня. Хорошее украшение цельно, то есть бриллианты в нём нельзя разделить на две части так, что ни одна проволока не соединяла бы камни из разных частей.
По существующей традиции в каждое украшение ювелир вкрапляет один фирменный изумруд с тремя ушками, к каждому из которых прикрепляется одна золотая перемычка. Таким образом, изумруд, например, позволяет скрепить между собой два или три любых бриллианта. Юпитерианский Фаберже всегда вставляет свой изумруд в центр украшения, юпитерианский Леонардо - ближе к левому нижнему углу. Однако эти изумруды - не только фирменный знак, но и возможность сэкономить на золоте, поэтому самые хитрые и дотошные ювелиры вставляют свой камень так, чтобо сократить расходы ценного металла. Своих изумрудов у мастера пруд пруди, так что можно считать, что они достаются ему бесплатно. Иногда, если добавление изумруда потребует дополнительных расходов на золото, или даже просто не принесёт выгоды, ювелиры жертвуют славой и обходятся без фирменной драгоценности.
Премьер-министр Юпитера каждый день требует от придворных ювелиров изготовить нове украшение для своей возлюбленной. Чтобы украшения не повторялись, обычно он сам придумывает их форму, то есть к моменту начала работы у ювелира есть план расположения всех камней. В последнее время премьеру показалось, что золота тратится слишком много, и он собирается нанять нового главного придворного ювелира. Старый мастер не хочет терять место, поэтому обратился к вам с просьбой помочь ему и составить оптимальную схему изготовления украшения (то есть такую, при которой будет потрачено меньше всего золотой проволоки).
Входные данные
В первой строке вводится целое число N - количество бриллиантов в украшении, которое требует изготовить премьер-министр. В следующих N строках заданы координаты бриллиантов в плане - по два числа на строке, разделённые пробелом.
Координаты во всех тестах - целые и не превосходят по модулю 10^4. Количество бриллиантов N не превышает 250.
Выходные данные
В первой строке выведите одно вещественное число - суммарную длину отрезков из золотой проволоки в оптимальном плане.
В следующей строке выведите два вещественных числа - координаты изумруда. В следующей строке выведите K- число бриллиантов, соединённых с изумрудом, затем K чисел - их номера. Номера не должны повторяться. Если в оптимальной строке изумруд отсутствует, K должно быть равно нулю, а координаты могут быть произвольными. Таким образом, K может быть равно 0, 2 или 3.
В следующей строке выведите число M - количество перемычек, соединяющих бриллианты. В следующих M строках выведите по два числа - номера бриллиантов, которые соединяет перемычка.
Бриллианты нумеруются от 1 до N.
Если верных ответов несколько, выведите любой.
Ваш ответ будет сравниваться с правильным с абсолютной или относительной точностью 10^{-6}.