The tragedy involving the Capulets and Montagues would not have happened in today’s age.
Given that all members of both gangs have smartphones with GPS, it is easy for the families to know where their members are. In a recent truce, the families decided to trust a foreign company to produce an app that would always display the closest distance between any two members of both families.
Due to the fact that this foreign company employs you as its personal slave, you have been entrusted with programing this app. You know that the modern city where this tragedy takes place is very geometric and, as such, all streets are orthogonal. Your program receives an entry for each person with its position on the 2D plane and the identifier of the family that person belongs to.
Your task is to print the minimum Manhattan distance between two members of the different families. The Manhattan distance between two points (x1, y1) and (x2, y2) is:
| |x1− x2| + |y1− y2|. |
You may assume that the points are spread out evenly over the space.
The input starts with an integer N that encodes the number of points. Each following line has 3 integers: X, Y, F encoding the point’s coordinates and its family. There will be at least one point in each family.
| 2 ≤ N ≤ 100 000 | Number of points |
| 0 ≤ X ≤ 1 000 000 000 | X coordinate of a point |
| 0 ≤ Y ≤ 1 000 000 000 | Y coordinate of a point |
| 0 ≤ F < 2 | Family id |
Your program should print the minimum Manhattan distance between two points of different families.
10 9 0 0 6 3 1 6 0 0 9 3 1 6 6 0 0 7 1 3 1 0 9 9 1 2 9 0 0 9 0
2