All Tracks>Algorithms> Graphs> Hamiltonian Path> Problem
Permutation of a query
★★★★★

2.5

20 votes
Hamiltonian Path, Algorithms, Graphs
Problem

You are given queries in the interval . There are eight possible moves and each of them costs  unit. Each move corresponds to add or subtract one for one of the coordinates.

Starting from the first query of the permutation, determine the permutation of query that can minimize the total cost and complete every query.

Input format

  • First line: denoting the queries
  • Next lines: Denoting the coordinate of the queries

Note: All queries have different coordinates.

Output format

Print the permutation of queries that minimize the total cost to complete all the queries.

Constraints

Sample Input
3
0 0 1 0
0 10 0 0
0 10 1 1
Sample Output
1 2 3
Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation

P1(0, 0, 1, 0) -> P2(0, 10, 0, 0): cost = abs(0 - 0) + abs(10 - 0) + abs(0 - 1) + abs(0 - 0) = 11
P2 (0, 10, 0, 0) -> P3 (0, 10, 1, 1): cost = abs(0 - 0) + abs(10 - 10) + abs(0 - 1) + abs(0 - 1) = 2

Total cost  = 11 + 2 = 13

Contributers:
Editor Image

?