题解

问题分析

题目要求找到一条直线 ( l )，使得平面上 ( n ) 个点到 ( l ) 的最大距离 ( D(l) ) 最小。这一问题等价于寻找点集的“最小宽度”，即能覆盖所有点的最窄条形区域的宽度（条形区域的边界是两条平行直线，宽度为两直线间的距离，此时最优直线为条形区域的中线）。

关键思路

1. 核心性质：
   最优直线 ( l ) 必然与点集的凸包相关——若点集存在凹点，凹点到直线的距离不会大于凸包顶点到直线的距离。因此，可先计算点集的凸包，仅通过凸包顶点求解最小宽度，大幅减少计算量。

2. 凸包与旋转卡壳：

   • 凸包计算：使用 Graham 扫描或 Andrew 算法，将点集压缩为凸多边形的顶点序列（复杂度 ( O(n \log n) )）。
   • 旋转卡壳：对于凸包的每条边，寻找离该边最远的顶点，计算该顶点到边的距离（即当前边对应的条形区域宽度）。所有边对应的最大距离的最小值，即为所求的最小 ( D(l) )。

3. 距离计算：
   点 ( (x_0, y_0) ) 到直线 ( ax + by + c = 0 ) 的距离公式为：
   [ \text{dis} = \frac{|ax_0 + by_0 + c|}{\sqrt{a^2 + b^2}} ]
   对于凸包的边（由两点 ( (x_1, y_1) ) 和 ( (x_2, y_2) ) 确定），直线方程可简化为 ( (y_1 - y_2)x + (x_2 - x_1)y + (x_1 y_2 - x_2 y_1) = 0 )，代入公式计算距离。

代码实现

import math

# 点类
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def __sub__(self, other):
        return Point(self.x - other.x, self.y - other.y)
    
    def cross(self, other):
        # 叉积
        return self.x * other.y - self.y * other.x
    
    def dist_sq(self, other):
        # 距离平方
        return (self.x - other.x)**2 + (self.y - other.y)** 2

# 计算凸包（Andrew算法）
def convex_hull(points):
    if len(points) <= 1:
        return points
    # 按x排序，x相同按y排序
    points = sorted(points, key=lambda p: (p.x, p.y))
    # 下凸包
    lower = []
    for p in points:
        while len(lower) >= 2 and (lower[-1] - lower[-2]).cross(p - lower[-1]) <= 0:
            lower.pop()
        lower.append(p)
    # 上凸包
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and (upper[-1] - upper[-2]).cross(p - upper[-1]) <= 0:
            upper.pop()
        upper.append(p)
    # 合并，去除重复点（首尾相同）
    return lower[:-1] + upper[:-1]

# 点到直线的距离（直线由两点a和b确定）
def point_to_line_dist(p, a, b):
    # 向量ab和ap的叉积的绝对值除以ab的长度
    ab = b - a
    ap = p - a
    cross = abs(ab.cross(ap))
    dist_ab = math.hypot(ab.x, ab.y)
    if dist_ab < 1e-8:
        return 0.0
    return cross / dist_ab

# 旋转卡壳计算最小宽度
def min_width(convex):
    n = len(convex)
    if n == 1:
        return 0.0
    if n == 2:
        # 两点，最小宽度为0（直线过两点）
        return 0.0
    min_d = float('inf')
    # 对每条边，找最远点
    j = 1  # 初始最远点索引
    for i in range(n):
        a = convex[i]
        b = convex[(i+1) % n]
        # 移动j到离边ab最远的点
        while True:
            c = convex[j]
            d = convex[(j+1) % n]
            # 比较c和d到ab的距离，选择更远的
            dist_c = point_to_line_dist(c, a, b)
            dist_d = point_to_line_dist(d, a, b)
            if dist_d > dist_c + 1e-8:
                j = (j + 1) % n
            else:
                break
        # 当前边对应的最大距离是dist_c
        current_d = point_to_line_dist(convex[j], a, b)
        if current_d < min_d:
            min_d = current_d
    return min_d

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    points = []
    for _ in range(n):
        x = int(input[ptr])
        y = int(input[ptr+1])
        points.append(Point(x, y))
        ptr += 2
    # 计算凸包
    hull = convex_hull(points)
    # 计算最小宽度
    width = min_width(hull)
    # 四舍五入到小数点后两位
    print("{0:.2f}".format(round(width, 2)))

if __name__ == "__main__":
    main()

复杂度分析

1. 凸包计算：Andrew 算法的时间复杂度为 ( O(n \log n) )，主要来自排序步骤。
2. 旋转卡壳：遍历凸包的每条边（数量为 ( O(h) )，( h ) 为凸包顶点数），每次移动最远点的索引 ( j )，总操作次数为 ( O(h) )。对于大规模点集，( h \ll n )（尤其当点集近似线性分布时），效率极高。
3. 总复杂度：( O(n \log n) )，可处理 ( n \leq 10^5 ) 的数据范围。

该方法通过凸包简化问题，结合旋转卡壳高效求解，准确得到最小最大距离 ( D(l) )。