Задачі
Юпітеріанські ювеліри
Юпітеріанські ювеліри
Планета Юпітер славиться своїми майстерними ювелірами. Найціннішими у всій Сонячній системі вважаються плоскі прикраси, які являють собою набір діамантів, з'єднані перемичками із золота. Перемичка - це прямий шматок дроту, що з'єднує два дорогоцінних каменю. Гарне прикраса цілісно, тобто діаманти у ньому не можна розділити на дві частини так, щоб жодна з перемичок не поєднувала б камені з різних частин.
За існуючою традицією у кожну прикрасу ювеліомр вкраплюється один фірмовий смарагд з трьома вушками, до кожного з яких прикріплюється одна золота перемичка. Таким чином, смарагд, наприклад, дозволяє скріпляти між собою два або три будь-які діаманти. Юпітеріанський Фаберже завжди вставляє свій смарагд у центр прикраси, юпітеріанський Леонардо - ближче до лівого нижнього кута. Однак ці смарагди - не тільки фірмовий знак, але й можливість заощадити на золоті, тому найхитріші і допитливі ювеліри вставляють свій камінь так, щоб скоротити витрати цінного металу. Своїх смарагдів у майстра греблю гати, так що можна вважати, що вони дістаються йому безкоштовно. Іноді, якщо додавання смарагду потребуватиме додаткових видатків на золото, або навіть просто не принесе вигоди, ювеліри жертвують славою і обходяться без фірмової коштовності.
Прем'єр-міністр Юпітера кожен день вимагає від придворних ювелірів виготовити нову прикрасу для своєї коханої. Щоб прикраси не повторювалися, зазвичай він сам придумує їх форму, тобто до моменту початку роботи у ювеліра є план розташування усіх каменів. Останнім часом прем'єру здалося, що золота витрачається занадто багато, і він збирається найняти нового головного придворного ювеліра. Старий майстер не хоче втрачати місце, тому звернувся до вас з проханням допомогти йому і скласти оптимальну схему виготовлення прикраси (тобто таку, при якій буде витрачено менше всього золотого дроту).
\InputFile
У першому рядку вводиться ціле число N - кількість діамантів у прикрасі, яку вимагає виготовити прем'єр-міністр. У наступних N рядках задані координати діамантів в плані - по два числа у рядку, відокремлені пропуском.
Координати в усіх тестах - цілі і не перевищують по модулю \textbf{10^4}. Кількість діамантів \textbf{N} не перевищує \textbf{250}.
\OutputFile
У першому рядку виведіть одне дійсне число - сумарну довжину відрізків із золотого дроту в оптимальному плані.
У наступному рядку виведіть два дійсних числа - координати діаманта. У наступному рядку виведіть \textbf{K} - число діамантів, з'єдинани зі смарагдом, потім \textbf{K} чисел - їх номери. Номери не повинні повторюватись. Якщо у оптимальному рядку смарагд відсутній, \textbf{K} повинно бути рівним нулю, а координати можуть бути довільними. Таким чином, \textbf{K} може бути рівним \textbf{0}, \textbf{2} або \textbf{3}.
У наступному рядку виведіть число \textbf{M} - кількість перемичок, які з'єднують діаманти. У наступних \textbf{M} рядках виведіть по два числа - номери діамантів, які з'єднує перемичка.
Діаманти нумеруються від \textbf{1} до \textbf{N}.
Якщо вірних відповідей декілька, виведіть довільну.
Ваша відповідь буже порівнюватись з вірною з абсолютною або відносною точністю \textbf{10^\{-6\}}.
Вхідні дані #1
3 0 0 4 0 0 3
Вихідні дані #1
6.7664325675 0.6957885341 0.7511761065 3 3 2 1 0