Art Academy V: Ruin

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 0.5s
Java 1.0s
Python 3.5s
Memory limit: 512M

Problem type

Long live the Queen!

After a heavy bombardment by the forces of Queen Alice, the Art Academy has started to collapse. Since hewmatt10, the faithful leader of the Art Academy, was so fanatical in his obsession for art, pieces have been hung everywhere; including on the ceiling. hewmatt10 has already managed to remove all his pieces on the walls, so he turns his salvation efforts to the sky, and prepares to catch the pieces as they fall. Fortunately for him, he is not alone. His loyal aide has come back to help him, and together, they will save the art!

The Academy will be represented on a 2D plane where N artworks will fall sequentially, given as a point (x_i, y_i). Either one of them must collect a given piece of art when it falls. Determine the minimum sum of the Manhattan distances that hewmatt10 and his aide will have to travel.

For example, if there is a single painting that falls, hewmatt10 starts at (1, 0), his aide starts at (5, 0), and the painting falls at (4, 4), the optimal Manhattan distance would be for his aide to move a distance of |5-4| + |0-4| = 5.

Input Specification

The first line will contain the integer N, representing the number of artworks that will fall.

The next line will have the integers H_x, H_y, A_x, and A_y, representing the (x, y) coordinates of where hewmatt10 and his aide will start.

The following N lines will have two integers x_i and y_i, representing the (x, y) coordinate of where the artwork will drop down to.


For all subtasks:

1 \le N \le 2\,000, -10^3 \le x_i, y_i, H_x, H_y, A_x, A_y \le 10^3

Subtask 1 [10%]

1 \le N \le 20

Subtask 2 [20%]

1 \le N \le 200

Subtask 3 [70%]

No additional constraints.

Output Specification

Save the Academy! Save the artwork! Output the minimum total distance hewmatt10 and his aide will have to travel in order to catch all the artwork.

Sample Input 1

1 1 4 4
3 3
1 0
5 2

Sample Output 1



  • 0
    AlanCCCL2S18  commented on Jan. 31, 2022, 10:46 p.m.

    I'm very confused. Why is my solution clearing the last subset but not the other two? Shouldn't the last one be harder?