Yet Another Contest 6 P5 - No More Coyotes

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 2.0s
Python 5.0s
Memory limit: 256M

Author:
Problem type

There are N sheep, labelled from 1 to N, who are in a field. Wary of coyotes, the sheep vow to protect each other by positioning themselves such that every sheep can see every other sheep.

The i-th sheep has a position of (X_i, Y_i) and has a 90 degree field of view. Their field of view is denoted by an integer, V_i, representing one of the following four fields of view:

  • If V_i = 0, then the i-th sheep can see the j-th sheep if and only if X_i \le X_j and Y_i \le Y_j.
  • If V_i = 1, then the i-th sheep can see the j-th sheep if and only if X_i \le X_j and Y_i \ge Y_j.
  • If V_i = 2, then the i-th sheep can see the j-th sheep if and only if X_i \ge X_j and Y_i \ge Y_j.
  • If V_i = 3, then the i-th sheep can see the j-th sheep if and only if X_i \ge X_j and Y_i \le Y_j.

Sheep can perform moves to reposition or reorient themselves. In one move, the i-th sheep can perform one of the following actions:

  • Move 1 unit in any of the four cardinal directions. That is, decrease X_i by 1, increase X_i by 1, decrease Y_i by 1, or increase Y_i by 1.
  • Rotate their field of view by 90 degrees. That is, change the field of view from V_i to (V_i+1) mod 4 or (V_i-1) mod 4.

What is the minimal total number of moves performed by the sheep such that every sheep can see every other sheep? Note that multiple sheep are allowed to have the same position.

Constraints

2 \le N \le 10^6

-10^9 \le X_i, Y_i \le 10^9

0 \le V_i \le 3

Subtask 1 [60%]

2 \le N \le 2\,000

Subtask 2 [40%]

No additional constraints.

Input Specification

The first line of input contains a single integer N, representing the number of sheep.

The i-th of the following N lines of input contains three space-separated integers, X_i, Y_i, V_i, representing the initial position and field of view of the i-th sheep.

Output Specification

On a single line, output the minimal total number of moves performed by the sheep such that every sheep can see every other sheep.

Sample Input

3
1 2 1
2 1 0
4 2 0

Sample Output

3

Explanation

It is optimal for the 1-st sheep to move to (2, 2), and for the 3-rd sheep to rotate their field of view twice such that V_3 = 2.


Comments

There are no comments at the moment.