高考问答神武手游珍兽怎么进阶:pascal usaco 2004 open april
来源：百度文库 编辑：高考问答 时间：2024/04/29 12:02:43
一年一度的饲料桶填充工作又要开始了，农民约翰要将他的农场中所有的饲料桶都装满。饲料桶的容量可能是不同的，而且经过一年，每个桶中剩余的饲料数量也不尽相同。有的桶是空的，有的是满的，也有的桶里有部分饲料。每个桶的容量和桶中饲料的量都是整数，在1到10000之间。饲料供应商的收费方式是：每次装满一个桶，收取固定的费用，不管装入的饲料多少。
为了省钱，农民约翰需要重新分配所有饲料桶中的剩余饲料，使得他要拿到饲料供应商那里的桶尽可能少。请帮助农民约翰，计算他最少要带多少桶去补充饲料。
输入：(barrels.in)
第一行是整数n，表示桶的个数，1<=n<=1000。
接下来的n行，每行两个整数a和b，分别表示一个桶中剩余的饲料和它的容量，0<=a<=b，1<=b<=10000。
输出：(barrels.out)
一个整数，表示最少要带去的桶数。
样例：
输入
4
0 1
4 5
0 2
1 2
输出
1
说明：
可将第二个桶中的4份饲料放入另外的3个桶，将它们都装满，只带第二个桶去补充饲料即可。
围栏(enclose USACO 2004 open april)
农民约翰的n头牛都有各自最喜欢的吃草区域，区域都是矩形，边都平行于坐标轴。农民约翰要为它们造一些围栏，使得更为安全，不受其他食肉动物的威胁。如果两个矩形有公共面积，就要合并，合并后仍旧是一个矩形，边都平行于坐标轴，而且面积最小。如下图所示
******** *************
* * * *
* * * *
* ++++++++++ -> * *
* + * + * *
***+**** + * *
+ + * *
++++++++++ *************
当然，新的矩形也有可能再和其他矩形合并。求最终有几个矩形和矩形的总面积。
输入：(enclose.in)
第一行是n，1<=n<=100。
接下来的n行，每行描述一个矩形。共4个整数，分别表示左下角和右上角的顶点坐标。坐标范围在0到10000之间。
输出：(enclose.out)
两个整数，用一个空格分开。分别表示最后的矩形数和矩形的总面积。
样例：
输入
3
0 0 5 2
8 8 9 9
2 1 6 4
输出
2 25
说明：两个矩形为(0, 0)-(6, 4)和(8, 8)-(9, 9)，总面积是6*4+1*1=25。
Enclose
var i,j,n,t,s,w,x,y,z:longint;
b:boolean;
a:array[1..100,1..8] of longint;
c:array[1..100] of boolean;
begin
assign(input,'enclose.in');reset(input);
assign(output,'enclose.out');rewrite(output);
readln(n);
for i:=1 to n do begin
readln(a[i,1],a[i,2],a[i,3],a[i,4]);
a[i,5]:=a[i,3];
a[i,6]:=a[i,2];
a[i,7]:=a[i,1];
a[i,8]:=a[i,4];
end;
while b=false do begin
b:=true;
for i:=1 to n-1 do
for j:=i+1 to n do
if (c[i]=false)and(c[j]=false) then begin
w:=a[i,3]-a[j,1];
x:=a[i,4]-a[j,2];
y:=a[i,5]-a[j,7];
z:=a[i,6]-a[j,8];
if ((w>0)and(x>0)and(y>0)and(z<0))or((w<0)and(x<0)and(y<0)and(z>0)) then begin
if a[j,1]<a[i,1] then a[i,1]:=a[j,1];
if a[j,2]<a[i,2] then a[i,2]:=a[j,2];
if a[j,3]>a[i,3] then a[i,3]:=a[j,3];
if a[j,4]>a[i,4] then a[i,4]:=a[j,4];
a[i,5]:=a[i,3];
a[i,6]:=a[i,2];
a[i,7]:=a[i,1];
a[i,8]:=a[i,4];
b:=false;
c[j]:=true;
end;
end;
end;
t:=0;s:=0;
for i:=1 to n do if c[i]=false then begin
t:=t+1;
s:=s+(a[i,3]-a[i,1])*(a[i,4]-a[i,2]);
end;
writeln(t,' ',s);
close(input);close(output);
end.