A5145 | $[COCR Cup 2025 B] Square$

时间限制3s

内存限制256MB

通过 / 提交0/0

题目描述

题目背景 $\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$ 个整数，表示与坐标轴平行的彩色矩形的最短周长。

输入 #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$。

C++ 编辑器

输入

输出