题解 P4864 【Jerry Loves Lines】

CYJian · 2018-09-01 21:19:08 · 题解

首先需要知道一个常识:两条直线相交后,这两条直线在交点右侧的大小关系就会改变.如果有多条直线计算排名,则会导致两条直线交换排名,且这两条直线在交点附近排名必然相邻.所以可以直接把这两条直线的一条排名+1,一条排名-1,这样就可以稳定过了..

这个应该算是常识吧..或者说很显然

然后对于这道题,我们就只要算出所有直线两两之间的交点并且按照x排好序,然后把询问离线排序处理.

先将所有点按照最靠左的询问排好序,然后每经过一个交点就把直线的排名更新一下.处理询问的时候就直接用排名为k的直线更新就好了.

代码

Updata (2018.9.21):

感谢 @打脸不疼 提供的Hack数据..

(但是数据中并没有加入这一组数据,请求管理员加入)

现在标算已修改,这里是代码