Optimal Route Finder

You are given a set of 2D points. Your task is to determine the optimal route that visits each point exactly once and then returns to the starting point. This problem is a naive version of the Traveling Salesman Problem (TSP) and can be solved by checking all possible permutations of the points.

The Euclidean distance between two points \( (x_1, y_1) \) and \( (x_2, y_2) \) is defined as \( \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} \). Your solution should compute the total distance of any route by summing the distances between consecutive points — including the distance from the last point back to the starting point.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer \( n \) (where \( n \geq 2 \)) representing the number of points.
• The next \( n \) lines each contain two space-separated integers \( x \) and \( y \), representing the coordinates of each point.
• The first point in the input is the starting point for the route (and must also be the ending point in the output).

outputFormat

The output should be written to stdout and consist of \( n+1 \) lines. Each line should contain two space-separated integers corresponding to the coordinates of the points in the optimal route, with the first and last points being identical to denote a complete circuit.

4
0 0
1 1
1 0
0 1

0 0
1 0
1 1
0 1
0 0