Permutation of a query

★★★★★

2.5

20 votes

Hamiltonian Path, Algorithms, Graphs

Details

Submissions

Discussion

Editorial

Problem

You are given $q$ queries in the interval $[x1, y1, x2, y2]$ . There are eight possible moves and each of them costs $1$ 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: $q$ denoting the queries
Next $q$ 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

$1 \le q \le 10^5\\ 0 \le x_1,\ x_2,\ y_1,\ y_2 \le 80$

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