水平线平分正方形总面积：事件斜率精确求切点

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练输入axis-aligned square(x,y,side)，整数y/side，side>0；切线水平，求下方总面积为一半的最小y。
• 每square面积独立相加，重叠重复计。题目只给平分面积方向线索，union/任意角度未给，应当待核变体。

解题路线

1. square在[y,y+side]内，下方面积随切高线性增长，斜率side。y加side斜率，y+side减side，按事件扫描面积积分。
2. 目标totalArea/2；在某段previous..current跨目标时，解previous+(target−area)/slope。用Fraction对整数输入保持精确。
3. 若刚好到目标且下一段斜率0，所有该空隙高度都平分，选最小previous。union版斜率需当前x区间并集长度，不是side之和，应另用sweep/区间覆盖树。

手动走一遍

square边2在y0和边2在y4，总面积8，低块在y2面积4，最小切高2，空隙2..4全部平分。两个完全重叠square各side2，相加总8，切高1；与union总4数值目标不同，虽这个例子切点恰相同。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from fractions import Fraction


def bisect_squares(squares):
    events={};total=0
    for x,y,side in squares:
        if type(side) is not int or side<=0 or type(y) is not int:raise ValueError("integer y and positive integer side required")
        events[y]=events.get(y,0)+side;events[y+side]=events.get(y+side,0)-side;total+=side*side
    if not total:return None
    target=Fraction(total,2);area=Fraction(0);slope=0;previous=None
    for y in sorted(events):
        if previous is not None:
            added=slope*(y-previous)
            if area==target:return Fraction(previous)
            if slope and area+added>=target:return previous+(target-area)/slope
            area+=added
        slope+=events[y];previous=y
    raise AssertionError("unreachable")

复杂度

n square排序O(nlogn)、扫描O(n)、空间O(n)，精确有理数算术位成本另计。union需更复杂的x覆盖结构。

易错点与追问

容易失分的边界

• 用n个square中心平均值一般不能平分面积，大小权重不同。
• 二分可行但要给误差合同，不能将近似小数称精确答案。

继续深挖

• union面积版如何维护cover count和covered x-length？
• 切线方向未限定时，有无限解，如何确定输出要求？