Jupiterian Jewelers
"'markdown Jupiter is famous for its master jewelers. The most prized ornaments in the entire Solar System are flat decorations, consisting of diamonds linked by gold bridges. A bridge is a straight piece of wire connecting two precious stones. A beautiful ornament is considered integral, meaning the diamonds cannot be split into two groups such that no bridge connects stones from different groups.
Traditionally, each ornament includes a signature emerald with three loops, each attached to a gold bridge. This allows the emerald to connect two or three diamonds. The Jovian Fabergé places his emerald at the center of the ornament, while the Jovian Leonardo positions it closer to the lower left corner. These emeralds are not just signature marks but also a way to save on gold, so the most resourceful jewelers position their emeralds to minimize the use of precious metal. The master has an ample supply of emeralds, so they are considered free. Sometimes, if adding an emerald would increase gold usage or offer no advantage, jewelers forgo the signature gem.
The Prime Minister of Jupiter requests a new ornament from the court jewelers daily for his beloved. To ensure uniqueness, he often designs their shape himself, so by the time work begins, the jeweler has a plan for the placement of all the stones. Recently, the Prime Minister noticed excessive gold usage and plans to hire a new chief court jeweler. The current master, eager to retain his position, seeks your help to create an optimal design for the ornament, minimizing the use of gold wire.
Input
The first line contains an integer ( N ) - the number of diamonds the Prime Minister requires in the ornament. The next ( N ) lines provide the coordinates of the diamonds in the plan, with two numbers per line separated by a space.
Coordinates in all tests are integers and do not exceed ( 10^4 ) in absolute value. The number of diamonds ( N ) does not exceed ( 250 ).
Output
On the first line, output one real number - the total length of the gold wire segments in the optimal plan.
On the next line, output two real numbers - the coordinates of the emerald. Then, output ( K ) - the number of diamonds connected to the emerald, followed by ( K ) numbers - their indices. Indices should not repeat. If the optimal plan does not include an emerald, ( K ) should be zero, and the coordinates can be arbitrary. Thus, ( K ) can be ( 0 ), ( 2 ), or ( 3 ).
On the next line, output the number ( M ) - the number of bridges connecting the diamonds. In the following ( M ) lines, output two numbers - the indices of the diamonds connected by a bridge.
Diamonds are numbered from ( 1 ) to ( N ).
If there are multiple correct answers, output any.
Your answer will be compared with the correct one with an absolute or relative precision of ( 10^-6 ). "'