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 winsty
program pku1765_sqybi;
const
nn = 40000;
e = 1e-6;
type
rec = record
x, p: longint;
end;
TSplayTree = object
root, num: longint;
data, father: array[1..nn]of longint;
son: array[0..1, 1..nn]of longint;
procedure init;
function height(x, y: longint): real;
function compare(x, y: longint): boolean;
procedure rotate(x, w: longint);
procedure splay(x, y: longint);
procedure addNode(x, y, z: longint);
procedure insert(y: longint);
function find(y: longint): longint;
procedure delete(y: longint);
function min: longint;
function succ(y: longint): longint;
end;
TGraph = object
m: longint;
head: array[0..nn]of longint;
adj, next: array[1..nn]of longint;
procedure init;
procedure addEdge(x, y: longint);
procedure dfs(x: longint);
end;
var
n, i, j, top: longint;
a: array[1..nn, 1..4]of longint;
b: array[1..nn*3]of rec;
water, directWater: array[0..nn]of longint;
tree: TSplayTree;
graph: TGraph;
function compare(r1, r2: rec): boolean; //a < b
var
x1, x2: longint;
begin
if r1.p = 2 then begin
if a[r1.x, 2] < a[r1.x, 4] then
x1 := a[r1.x, 1]
else
x1 := a[r1.x, 3];
end
else
x1 := a[r1.x, r1.p];
if r2.p = 2 then begin
if a[r2.x, 2] < a[r2.x, 4] then
x2 := a[r2.x, 1]
else
x2 := a[r2.x, 3];
end
else
x2 := a[r2.x, r2.p];
compare := (x1 < x2) or ((x1 = x2) and (r1.p < r2.p));
end;
procedure qsort(l, r: longint);
var
i, j: longint;
d, t: rec;
begin
i := l;
j := r;
d := b[(l+r) div 2];
repeat
while compare(b[i], d) do inc(i);
while compare(d, b[j]) do dec(j);
if i <= j then begin
t := b[i];
b[i] := b[j];
b[j] := t;
inc(i);
dec(j);
end;
until i > j;
if l < j then qsort(l, j);
if i < r then qsort(i, r);
end;
procedure TSplayTree.init;
begin
root := 0;
num := 0;
end;
function TSplayTree.height(x, y: longint): real;
begin
height := a[x, 2] + (y - a[x, 1]) / (a[x, 3] - a[x, 1]) * (a[x, 4] - a[x, 2]);
end;
function TSplayTree.compare(x, y: longint): boolean; //x < y
var
t: array[1..4]of longint;
i, j: longint;
h1, h2: real;
begin
t[1] := a[x, 1];
t[2] := a[x, 3];
t[3] := a[y, 1];
t[4] := a[y, 3];
for i:=1 to 3 do
for j:=i+1 to 4 do
if t[i] > t[j] then begin
t[i] := t[i] xor t[j];
t[j] := t[i] xor t[j];
t[i] := t[i] xor t[j];
end;
h1 := height(x, t[2]);
h2 := height(y, t[2]);
compare := h1 > h2;
end;
procedure TSplayTree.rotate(x, w: longint);
var
y: longint;
begin
y := father[x];
son[1-w, y] := son[w, x];
if son[w, x] <> 0 then
father[son[w, x]] := y;
father[x] := father[y];
if father[y] <> 0 then
if son[0, father[y]] = y then
son[0, father[y]] := x
else
son[1, father[y]] := x;
father[y] := x;
son[w, x] := y;
end;
procedure TSplayTree.splay(x, y: longint);
begin
while father[x] <> y do begin
if father[father[x]] <> y then begin
if father[x] = son[0, father[father[x]]] then begin
if x = son[0, father[x]] then begin
rotate(father[x], 1);
rotate(x, 1);
end
else begin
rotate(x, 0);
rotate(x, 1);
end;
end
else begin
if x = son[1, father[x]] then begin
rotate(father[x], 0);
rotate(x, 0);
end
else begin
rotate(x, 1);
rotate(x, 0);
end;
end;
end
else
if x = son[0, father[x]] then
rotate(x, 1)
else
rotate(x, 0);
end;
if y = 0 then root := x;
end;
procedure TSplayTree.addNode(x, y, z: longint);
begin
data[num] := z;
father[num] := y;
son[0, num] := 0;
son[1, num] := 0;
end;
procedure TSplayTree.insert(y: longint);
var
x: longint;
begin
if root = 0 then begin
inc(num);
root := num;
addNode(num, 0, y);
exit;
end;
x := root;
repeat
if compare(y, data[x]) then begin
if son[0, x] = 0 then break;
x := son[0, x];
end
else begin
if son[1, x] = 0 then break;
x := son[1, x];
end;
until false;
inc(num);
addNode(num, x, y);
if compare(y, data[x]) then
son[0, x] := num
else
son[1, x] := num;
x := num;
splay(x, 0);
end;
function TSplayTree.find(y: longint): longint;
var
x: longint;
begin
x := root;
repeat
if data[x] = y then break;
if compare(y, data[x]) then
x := son[0, x]
else
x := son[1, x];
until false;
find := x;
end;
procedure TSplayTree.delete(y: longint);
var
x, z: longint;
begin
x := find(y);
splay(x, 0);
if son[0, x] = 0 then begin
if son[1, x] = 0 then
init
else begin
root := son[1, x];
father[son[1, x]] := 0;
end;
end
else begin
z := son[0, x];
while son[1, z] <> 0 do z := son[1, z];
splay(z, x);
father[z] := 0;
root := z;
son[1, z] := son[1, x];
if son[1, z] <> 0 then
father[son[1, z]] := z;
end;
end;
function TSplayTree.min: longint;
var
x: longint;
begin
min := 0;
if root = 0 then exit;
x := root;
while son[0, x] <> 0 do x := son[0, x];
splay(x, 0);
min := data[x];
end;
function TSplayTree.succ(y: longint): longint;
var
x: longint;
begin
x := find(y);
splay(x, 0);
x := son[1, x];
succ := 0;
if x = 0 then exit;
while son[0, x] <> 0 do x := son[0, x];
succ := data[x];
end;
procedure TGraph.init;
begin
m := 0;
fillchar(head, sizeof(head), 0);
end;
procedure TGraph.addEdge(x, y: longint);
begin
inc(m);
adj[m] := y;
next[m] := head[x];
head[x] := m;
end;
procedure TGraph.dfs(x: longint);
var
temp: longint;
begin
water[x] := directWater[x];
if head[x] = 0 then exit;
temp := head[x];
while temp <> 0 do begin
if water[adj[temp]] = -1 then dfs(adj[temp]);
water[x] := water[x] + water[adj[temp]];
temp := next[temp];
end;
end;
begin
readln(n);
for i:=1 to n do begin
readln(a[i, 1], a[i, 2], a[i, 3], a[i, 4]);
b[i*3-2].x := i; //segment no.
b[i*3-2].p := 1; //type
b[i*3-1].x := i;
b[i*3-1].p := 3;
if a[i, 2] < a[i, 4] then begin
b[i*3].x := i;
b[i*3].p := 2;
end
else begin
b[i*3].x := i;
b[i*3].p := 2;
end;
end;
qsort(1, n*3);
tree.init;
graph.init;
tree.insert(b[1].x);
j := 1;
for i:=2 to n*3 do begin
if b[i].p <> 2 then begin
top := tree.min;
directWater[top] := directWater[top] + (a[b[i].x, b[i].p] - a[b[j].x, b[j].p]);
j := i;
end;
case b[i].p of
1: tree.insert(b[i].x);
2: graph.addEdge(tree.succ(b[i].x), b[i].x);
3: tree.delete(b[i].x);
end;
end;
fillchar(water, sizeof(water), -1);
graph.dfs(0);
for i:=1 to n do
writeln(water[i]);
end.
阅读(183 次)