HDU 6681 – Rikka with Cake

题目链接:HDU 6681

根据欧拉定理,推得答案等于交点数量加一。

下面问题变成了二维平面上有一些于坐标轴垂直的线段,求交点个数。这是一个经典的问题。

首先我们要把点的坐标离散化,注意为了加速二分的过程,可以把横坐标和纵坐标分别离散化。

接着我们把这些线段分成两类:与$x$轴平行的和与$y$轴平行的。我们需要枚举从左到右(意味着需要排序)每一根垂直于$x$轴的线段,然后对于每一根线段,在垂直于$y$轴的线段几何中,将左端点的横坐标小于或等于它的点的右端点的横坐标扔进小根堆(意味着需要排序),并对这些线段的纵坐标所在的位置加一(树状数组或线段树维护)。接着我们需要把小根堆顶部左右的右端点小于当前枚举的$x$的删掉,并并对这些线段的纵坐标所在的位置减一。那么当前的于$x$垂直的线段上的交点个数为这个线段的起点纵坐标和重点纵坐标对应的树状数组(或线段树)的一个区间和。

所以我们只需要依次枚举所有的$x$,将区间和叠加到答案上即可。

时间复杂度$O(n \log n)$。

 

 

说点什么

avatar
50
  Subscribe  
提醒