POJ 1765 — November Rain
话说也是攒了好久的题了…今天终于AC了.是CEOI 2003的一道题,SPOJ和POJ上都有.
一道平衡树的题目,用Splay做到了POJ Pascal组第10,SPOJ Pascal组第12.不过Nxun是POJ Pascal组第6,SPOJ Pascal第9…
题目描述么…看我和hrm的这段聊天记录:
hrm 22:51:49什么题啊？Killa.sqybi 22:52:26就是说…一堆屋顶,给出两个端点的坐标,然后任意两个屋顶不相交或者相连Killa.sqybi 22:52:31天上下雨Killa.sqybi 22:52:39问每个屋顶能接到多少雨Killa.sqybi 22:52:44雨会向下流Killa.sqybi 22:52:48就这道题..hrm 22:53:31噢。我退化了hrm 22:53:37不懂为什么用splay了hrm 22:53:45输入是什么啊Killa.sqybi 22:54:30第一行是屋顶数n 接下来n行每行四个数 分别是屋顶左右端点的x y坐标hrm 22:56:11然后呢？每一滴雨的坐标？Killa.sqybi 22:56:39哦..我忘了说每个单位长度落下一滴雨hrm 22:56:57。。。。。hrm 22:57:39那直接用面积不就知道每个屋顶接多少雨了么Killa.sqybi 22:58:02不是..雨会被上面的屋顶挡住..而且会从上面的屋顶比较矮的那边流下来
嗯,就是这样.然后呢,做法就是,从左边开始,用一条扫描线对每个线段的端点进行扫描.每条线段对应三个事件:第一个是左端点,对应线段进入扫描线上的序列;第二个是线段右端点,对应线段离开;第三个是线段比较低的一端,对应的是向下流水.然后,因为两条线段的重叠部分,一条总是高于另一条而不会改变(否则就会相交),所以可以用Splay维护一个线段的序列.最后只要先扫描一遍,同时用一个图记录每条线段的流水情况(流到哪条线段,程序中为了实现方便把边反向),然后进行拓补排序(或者DFS)就可以.
刚才在POJ上AC之后,到SPOJ上死活都TLE.而Nxun在SPOJ上AC的程序,到POJ死活都RE.最后发现了问题,SPOJ是多组数据,而POJ是一组…
{ POJ 1765; SPOJ 86; November Rain - sqybi’s code - Splay - 创建事件点,从左向右扫描,每次维护当前扫描线上所有线段的排序}//for my winstyprogram pku1765_sqybi; const nn = 40000; e = 1e-6;
type rec = record x, p: longint; […]