首先最容易想到的就是N2暴力枚举所有线段去找最小值，但是这样会做了许多无用功。我们可以先对线段排序，使得线段最左侧的端点按照x轴y轴排序，然后我们可以限定在这个线段的矩形框内的所有线段才有可能产生最小值，每次查询对于第i条线段的最近距离，如果第j条线段的最左侧点的x与第i条线段的最右侧点的x差值大于ans，那么可以直接break，之后枚举是没有任何意义的，一定会大于ans，所以加了这部分剪枝复杂度就压缩了很大部分。首先最容易想到的就是N2暴力枚举所有线段去找最小值，但是这样会做了许多无用功。我们可以先对线段排
阅读背景：
HDU 6697 Closest Pair of Segments（线段距离）
来源：互联网
分享到：
