A71106.[COCR Cup 2025 B] Square

题目背景

$\color{black}{\mathtt{HS}}$：“彩旗拔旗赛即将开始！请各位选手在广场上就位！”

$\color{blue}{\mathtt{JW}}$：“FM，快帮我看看怎么走才能最快获得三面旗！”

$\color{red}{\mathtt{FM}}$：“让我看看，有了！你就拔 $1,3,7$ 号旗吧！”

$\color{blue}{\mathtt{JW}}$：“太好了，谢谢你！”

NH 也参加了这个比赛，快来帮他吧！

---

题目描述

广场上存在 $N$ 个点。每个点要么是红色、蓝色或绿色。

如果一个矩形内部或边缘上包含每种颜色的一个或多个点，则称该矩形为彩色矩形。你的任务是找到一个周长最短的与坐标轴平行的彩色矩形。与坐标轴平行的线段被视为退化的矩形，其周长为线段长度的两倍。

第 $1$ 行包含 $1$ 个整数 $N$，表示平面上点的数量。

接下来的 $n$ 行中，每行包含三个整数 $x_i,y_i,c_i$。每行表示在坐标 $(x_i,y_i)$ 处有一个颜色为 $c_i$ 的点（$0$：红色，$1$：蓝色，$2$：绿色）。

保证每种颜色至少有一个点，并且没有两个点具有相同的坐标。

在 $1$ 行中输出 $1$ 个整数，表示与坐标轴平行的彩色矩形的最短周长。

对于 $100\%$ 的数据，保证：

• $3 \le N \le 2 \times 10^5$
• $0 \le c_i \le 2$
• $0 \le x_i,y_i \le 10^8$

测试点编号	$N\le$
1~4	$200$
5~12	$2\times 10^3$
13~20	$2\times 10^5$

【样例解释】

样例组 #1：选择点 $1,3,4$ 即可获得一个左下角为 $(2,0)$ 右上角为 $(4,2)$ 的矩阵，答案为 $8$。