DP - Problem: Forming Quiz Teams

Forming Quiz Teams

You have been given the job of forming the quiz teams for the next MCA CPCI Quiz Championship. There are $$n = 2k$$ students interested to participate and you have to form $$k$$ teams, each team consisting of two members. Since the members have to practice together, all the students want their members house as near as possible. Let $$x_1$$ be the distance between the houses of group 1, $$x_2$$ be the distance between the houses of group 2 and so on. You have to make the groups so that $$x_1 + x_2 + \ldots + x_{k}$$ is minimized.

Example:

The following image shows the first sample test case where $$n = 4$$ and having student houses at positions $$(1, 1), (1, 3), (6, 8)$$ and $$(8, 6)$$. If we pair the students as shown in blue we get the minimum total distance. The orange pairing shows another possible pairing which is not optimal. Input

• One line with one integer $$n$$ giving the number of students.
• $$n$$ lines each with two integers $$x_i, y_i$$ giving the coordinates of the students houses.

Output

One line with a number giving the minimum total distance if we pair the students in an optimal way.

Limits

• $$n = 2k$$ where $$1 \leq k \leq 8$$
• $$0 \leq x_i, y_i \leq 1000$$

Sample Test Cases

Sample input 1

Sample output 1

Sample input 2

Sample output 2

Sample input 3

Sample output 3

Sample input 4

Sample output 4

Max file size: 1.0MB
Allowed extensions: .java, .cpp, .py