horizontally专题

POJ 1436 Horizontally Visible Segments 线段树

题目大意是,给出了很多条平行于y轴的线段,然后定义,两条线段能互相‘看见’的条件是,两条线段能由一条水平线连接,且这条水平线不能跟其他的所有线段有交点。 而题目要求的是,3个线段能互相看见,这个条件下有多少组不同的。 然后就能明显的感觉到是区间覆盖问题了。但是有一个细节问题,就是中间的水平线不一定经过整点,所以即使这个区间的所有点都被覆盖,也不能说其就不能穿过一条线,于是,可以将所有线段的长度