Problem Description: Smoothie Expressway

Due to the way customer lines like PA$2$ are being managed, customers are becoming impatient, leading to a loss of clientele.

The store managers of all of our stores in the city came to you with an idea to connect pairs of stores using a

dedicated expressway. In that case if the waiting time is long in one store, customers can go from one store to

another store using that expressway in a short amount of time without taking typical slower public road. Naturally,

it would only be fair if each of the stores was connected to exactly one another. However, constructing those

expressways are expensive. You have decided to proceed with the project only if the following conditions are met:

$1.$ There are n expressways connecting $2$n stores.

$2.$ Each store is connected to only one expressway.

$3.$ The pairs of stores must be matched in a way that minimizes the total distance of the expressways.

Assume that the distance of a expressway built between stores located at $($xi$,$ yi$)$ and $($xj$,$ yj$)$ is

$()2+()2.$

Write a program to determine this minimum sum of expressway distances so that your store managers are

satisfied!

The Problem

Given the $($x$,$ y$)$ positions of $2$n stores, of all possible ways to create n pairs of distinct stores, find the minimum

possible sum of distances between each stores in the pairs.

The Input $($to be read from standard input using scanf $($do not use file i$/$o$.$ Using file i$/$o will get zero$)$

The first line will contain a single positive integer, c $($c $<=25),$ representing the number of test cases to process.

The test cases follow.

The first line of input for each case will contain a single positive integer, n $($n $<=8),$ representing that there are $2$n

stores in total.

The following $2$n lines of each input case will contain a pair of space separated positive integers, xi and yi$,$

representing that the ith store is located at the coordinate $($xi$,$ yi$),$ with $-10000<=$ xi$,$ yi $<=10000.$ Additionally, the

line will also contain the name of the store $($a single word string with maximum $20$ characters$).$

The Output $($to be printed in standard console output $($do not use file i$/$o$.$ Using file i$/$o will get zero$))$

For each input case, output a single floating point number rounded to exactly $3$ decimal places, representing the

minimum sum of distances possible if the expressways are built between pairs of stores. After printing the sum,

print n lines with the pairs store names and their distance that gave the minimum sum of distance. The output has

to be in the following format: $($from store name, to store name, distance in exactly $3$ decimal places$).$ The "from store"

should be the store that appeared first in the input compared to the $"$to store". The order of the store names should match the

order they appeared in the input. If multiple sets of pairs result in the same minimum distance, print only the set that comes

first in the permutation based on the input order. Ensure your output exactly matches CodeGrade's output.

Sample Input

$2$

$1$

$19-18$ STOREA

$16-14$ STOREB

$3$

$010$ SMOTHIEKING

$100$ SMOTHIEQUEEN

$1010$ SMOOTHIEPRINCE

$1515$ SMOOTHIEPRINCES

$00$ SMOTHIEPALACE

$-5-5$ SMOTHIEKINGDOM

Sample Output

$5\mathrm{.}000$

$($STOREA$,$ STOREB, $5\mathrm{.}000)$

$28\mathrm{.}284$

$($SMOTHIEKING$,$ SMOTHIEQUEEN, $14\mathrm{.}142)$

$($SMOOTHIEPRINCE$,$ SMOOTHIEPRINCES, $7\mathrm{.}071)$

$($SMOTHIEPALACE$,$ SMOTHIEKINGDOM, $7\mathrm{.}071)$

Implementation Restrictions

$1.$ You must use the permutation $$used$$ array technique in your solution

$2.$ There are three tiers of credit for this program. If you can get the code to run fast enough for n $=5,$ then that's

worth $80\%$ of the points. If you can get it to run fast enough for n $=6,$ that's worth $95\%$ of the points, and for

full credit, it has to run fast for n $=8.$

$3.$ For most part of the code like for n$=5,$ you are not allowed to use chatgpt. You should use the permuation

code discussed in the class and modify it to solve this problem. However, for optimizing the code for n$=6$ or

more, you must explore how chatgpt can help you to optimize your code and you must submit a report with

your finding that should contain:

a$.$ Your code that runs fast enough for n$=5$

b$.$ Screenshot of the prompt and response from chagpt that helped you to improve your code to run faster

with n$=6$ or more.

$4.$ It's completely okay if you don't find a solution that runs fast enough for n $=8.$ You will not lose much credit.

My expectation is that students will be able to solve the problem for n $=5.$ I am curious to see how many can

solve it for n $=6$ and n $=8.$

$5.$ Your permutation must be a recursive code.

$6.$ You are allowed to use only two global variables. No other global variables are allowed:

a$.$ One for array of stores

b$.$ One for the final set of permutation int array that stores the index of the stores that gave you the

minimum distance

Deliverables

You must submit four files over codegrade:

$1)$ A source file, main.c$.$

$2)$ A file describing how you have used chatgpt to optimize your code for n