逼近暗影

小房间中央的矿区地图上，红色和蓝色的光点交织在一起，像一张正在流血的网。红色是Zero的守卫部署，蓝色是反抗军的隐蔽点。你们需要找到最近的一对跨色点——如果某个隐蔽点和守卫的距离太近，那个隐蔽点就可能已经暴露了。

"咋个找？"CC问，"一个个量？那要量到明年。"

"切地图。"你蹲下来，用手指在地图上画了一条竖线，"把地图分成左右两半。最近的跨色点对有三种可能——都在左边、都在右边、或者跨在分界线两边。"

Echo飘过来："左右两半可以继续切下去，直到只剩一两个点。关键是分界线附近——如果左右两边各自最近的距离是 $d$，那跨在分界线上的两个点，它们的上下距离不会超过 $d$。"

"对。"你说，"按上下坐标排好后，每个点只需要和它后面几个邻近的点比较。"

CC看着你画分割线，忽然说："这像切蛋糕。"

"啥子？"

"把大蛋糕切成两半，两半再切两半。切到每块只有一点点，然后找最小的一块。"

"差不多。"

你开始写。先把所有点按左右位置排好，然后一片一片切下去——找左半边的最近跨色对，找右半边的最近跨色对，取较小的那个作为基准。然后检查分界线附近的狭长地带，按上下坐标排好，每个点和后面几个邻近的点算距离。

屏幕上跳出了结果。最近跨色点对的距离是47米。

"47号坑道。"Echo说，"老周和陈叔……可能关在那里。"

题目描述

平面上 $n$ 个点，每个点有颜色。求最近的一对异色点的距离。

输入格式

$n$。然后 $n$ 行，每行坐标和颜色。

输出格式

最近异色点对的距离。

输入样例

2
0 0
0 3

输出样例

0

提示

• 按x坐标排序，分治处理左右两半。
• 跨中间线的点对，按y坐标排序后每个点只需和后面常数个点比较。
• 时间复杂度 $O(n \log n)$。

47号坑道第三层的入口处，立着一排休眠的机械守卫——它们不是Zero的，是反抗军留下的旧型号，被Zero俘获后重新编程。Echo说如果能重新激活它们，就能让它们反过来对付Zero的部队。

"但重新激活需要匹配。"Echo飘到第一个守卫前，投影被守卫胸口的蓝光染成了淡青色，"每个守卫有处理能力和耐久度两个参数。每个激活任务也有对应的难度和强度要求。只有守卫的参数同时大于等于任务要求，才能成功激活。"

"那就配对。"CC说，"难的任务给强的守卫，简单的任务给弱的守卫。"

"对。"你说，"但不能浪费——如果一个强守卫能做简单的任务，就不应该浪费它做难的任务。把好钢用在刀刃上。"