机智黄豆

文章
8
资源
0
加入时间
2年10月21天

Counting Intersections HDU - 5862 (离散化+树状数组扫描线段)

题目来源:Counting Intersections题意给你n条与坐标轴平行的线段,问有几个交点。数据保证没有重合的、长度为0的线段,没有共起点共终点的线段。思路由于所有线段都是和坐标轴平行的,所以可以把与x轴平行的线段和y轴平行的线段分开来看,将横着的线段纵坐标插入树状数组中,求所有竖着的线段起点到终点的区间和即为答案。求解的过程需要按照横坐标从小到大排序,横线段的点优先。...