题意：小明在旅游的路上看到了一条美丽的河，河上有许多船只，有的船只向左航行，有的船只向右航行。小明希望拍下这一美丽的风景，并且把尽可能多的船只都完整地拍到一张照片中。
小明位于河的边上，并且可以在河边的任意位置进行拍照，照相机的视野恰好为90度角，只能以垂直于河边的方向进行拍照。河上的船只全都可看作是平行于河边的一条线段，跟河边的距离各不相同，有的正在向左移动，有的正在向右移动，但移动速度恰好都是一样的。小明可以等待恰当的时间让尽量多的船只都走进照相机的视野里，你不需要考虑船只之间会互相遮挡视野的情况。
下面T组数据，对于每组数据：
第一行是一个数n(1≤n≤104)，表示船只的数量。
接下来n行，每行四个整数
x,y,z,d(−10^6≤x<y≤10^6,1≤z≤104)，表示船只的左端点位置、右端点位置、距离河边的距离，以及航行的方向。d为−1表示向左航行，1表示向右航行。
思路：首先画图
发现船[x,y,z]只有在[y-z,x+z]的区域内能看到
然后因为速度一样，则向同一方向的船只的相对位置是一样的，可以把它们看成线段
正着做一次前缀和，反着做一次，求两个前（后）缀和之和的最大值即可
哈希新姿势
1 var a,b,c,d,f1,f2,g1,g2,h:array[1..30000]of longint; 2 hash:array[-1500000..1500000]of longint; 3 cas,v,n,m,i,tmp,ans,s1,s2,n1,up,x1,y1,z1,d1:longint; 4 5 procedure swap(var x,y:longint); 6 var t:longint; 7 begin 8 t:=x; x:=y; y:=t; 9 end; 10 11 function max(x,y:longint):longint; 12 begin 13 if x>y then exit(x); 14 exit(y); 15 end; 16 17 procedure qsort(l,r:longint); 18 var i,j,mid:longint; 19 begin 20 i:=l; j:=r; mid:=h[(l+r)>>1]; 21 repeat 22 while mid>h[i] do inc(i); 23 while mid<h[j] do dec(j); 24 if i<=j then 25 begin 26 swap(h[i],h[j]); 27 inc(i); dec(j); 28 end; 29 until i>j; 30 if l<j then qsort(l,j); 31 if i<r then qsort(i,r); 32 end; 33 34 begin 35 assign(input,'hdoj5714.in'); reset(input); 36 assign(output,'hdoj5714.out'); rewrite(output); 37 readln(cas); 38 for v:=1 to cas do 39 begin 40 readln(n1); 41 up:=0; n:=0; m:=0; 42 for i:=1 to n1 do 43 begin 44 readln(x1,y1,z1,d1); 45 if y1-z1<=x1+z1 then 46 begin 47 inc(n); a[n]:=y1-z1; b[n]:=x1+z1; d[n]:=d1; 48 inc(m); h[m]:=y1-z1; 49 inc(m); h[m]:=x1+z1; 50 end; 51 end; 52 if m>0 then qsort(1,m); 53 for i:=1 to m do 54 if hash[h[i]]=0 then 55 begin 56 inc(up); hash[h[i]]:=up; 57 end; 58 fillchar(f1,sizeof(f1),0); 59 fillchar(f2,sizeof(f2),0); 60 fillchar(g1,sizeof(g1),0); 61 fillchar(g2,sizeof(g2),0); 62 for i:=1 to n do 63 if d[i]=1 then 64 begin 65 inc(f1[hash[a[i]]]); 66 dec(g1[hash[b[i]]]); 67 end 68 else 69 begin 70 inc(f2[hash[a[i]]]); 71 dec(g2[hash[b[i]]]); 72 end; 73 s1:=0; s2:=0; ans:=0; tmp:=0; 74 for i:=1 to up do 75 begin 76 s1:=s1+f1[i]; 77 tmp:=max(tmp,s1); 78 s1:=s1+g1[i]; 79 s2:=s2+f2[i]; 80 ans:=max(ans,tmp+s2); 81 s2:=s2+g2[i]; 82 end; 83 writeln('Case #',v,':'); 84 writeln(ans); 85 for i:=1 to m do hash[h[i]]:=0; 86 end; 87 88 close(input); 89 close(output); 90 end.