acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 竞赛
  • 讨论
  • 团队
  • 商城
登录
注册
题目详情提交记录(0)
  • A1499题解

    问题分析 核心需求:判断一条垂直直线 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

    userId_undefined
    雪
    空间掌握者时空双修者时间刺客
    0阅读
    0回复
    0点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页