21929번 - Colorful Rectangle 다국어

문제

You are given a set of points on a plane. Each point is colored either red, blue, or green. A rectangle is called colorful if it contains one or more points of every color inside or on its edges. Your task is to find an axis-parallel colorful rectangle with the shortest perimeter. An axis-parallel line segment is considered as a degenerated rectangle and its perimeter is twice the length of the line segment.

입력

The input consists of a single test case of the following format.

n
x1 y1 c1
.
.
.
xn yn cn

The first line contains an integer n (3 ≤ n ≤ 10⁵) representing the number of points on the plane. Each of the following n lines contains three integers x_i, y_i, and c_i satisfying 0 ≤ x_i ≤ 10⁸, 0 ≤ y_i ≤ 10⁸, and 0 ≤ c_i ≤ 2. Each line represents that there is a point of color c_i (0: red, 1: blue, 2: green) at coordinates (x_i, y_i). It is guaranteed that there is at least one point of every color and no two points have the same coordinates.

출력

Output a single integer in a line which is the shortest perimeter of an axis-parallel colorful rectangle.

제한

힌트