컬러풀 직사각형

시간 제한10초메모리 제한512 MB

요약

평면 위의 색깔 있는 점들이 주어질 때, 빨강, 파랑, 초록 점을 각각 최소 하나씩 포함하는 축 평행 직사각형의 둘레 최솟값을 구합니다.

난이도: 어려움10점 중 8점
유형: 세그먼트 트리, 정렬, 투 포인터
정답자: 아직 제출이 없습니다

문제

평면 위에 점들이 주어진다. 각 점은 빨간색, 파란색, 초록색 중 하나로 칠해져 있다. 변이 축에 평행한 직사각형이 내부 또는 경계 위에 모든 색의 점을 하나 이상 포함하면 그 직사각형을 colorful하다고 한다. colorful한 축 평행 직사각형 중 둘레가 가장 짧은 것을 찾아라. 축에 평행한 선분은 퇴화된 직사각형으로 보며, 그 둘레는 선분 길이의 2배이다.

입력

첫 줄에 정수 $n$ ( $3 \le n \le 10^5$ )이 주어진다. 이어지는 $n$ 개의 줄에는 정수 $x_i$ , $y_i$ , $c_i$ 가 주어지며, 이는 좌표 $(x_i, y_i)$ 에 색 $c_i$ 의 점이 있다는 뜻이다 ( $0 \le x_i \le 10^8$ , $0 \le y_i \le 10^8$ , $0 \le c_i \le 2$ ). 색 0은 빨강, 1은 파랑, 2는 초록이다. 모든 색의 점이 적어도 하나씩 있으며, 같은 좌표를 가진 두 점은 없다.

출력

colorful한 축 평행 직사각형의 둘레 최솟값을 정수 하나로 출력한다.

예제2

예제 1
입력
```
4
0 2 0
1 0 0
1 3 1
2 4 2
```
예상 출력
```
8
```
예제 2
입력
```
4
0 0 0
0 1 1
0 2 2
1 2 0
```
예상 출력
```
4
```