矩形分割CCF数组练习9

Question

平面上有一个大矩形，其左下角坐标 (0,0)，右上角坐标 (R,R)。大矩形内部包含一些小矩形，小矩形都平行于坐标轴且互不重叠。所有矩形的顶点都是整点。要求画一根平行于y轴的直线x=k（ k 是整数)，使得这些小矩形落在直线左边的面积必须大于等于落在右边的面积，且两边面积之差最小。并且，要使得大矩形在直线左边的的面积尽可能大。注意：若直线穿过一个小矩形，将会把它切成两个部分，分属左右两侧。
C++

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

【解题思路】：使用扫描线算法，记录并处理每条扫描线上的矩形边界。