问题分析
核心需求:判断一条垂直直线 x=c或水平直线 y=c是否能真正分割一个三角形(分割后两部分面积都 > 0)。
关键结论:
1.垂直分割 x=c:三角形被真正分割 ⇨ 三角形的最小 x 坐标 < c < 最大 x 坐标
2.水平分割 y=c:三角形被真正分割 ⇨ 三角形的最小 y 坐标 < c < 最大 y 坐标
(证明:若三角形 x 范围是 [minx, maxx],直线 x=c 在区间内部,必然穿过三角形内部,分割出两个非零面积区域)
解题思路
1.预处理每个三角形:计算min_x, max_x, min_y, max_y
2.把所有三角形的min_x/max_x存入两个数组,min_y/may_y存入两个数组
3.对这四个数组排序
4.对于每个查询:
x=c:答案 = 总三角形数 - (min_x>= c 的数量) - (max_x <= c 的数量)
y=c:答案 = 总三角形数 - (min_y>= c 的数量) - (max_y <= c 的数量)
5.用二分查找快速统计数量,时间复杂度 O (NlogN + MlogN),完美适配 N,M=1e5