论坛: 编程破解 标题: 绝对高手级题目（语言不限，最好是Pascal） 复制本贴地址    
作者: dyx [dyx]    论坛用户   登录
这是USACO的2.1的第一道。
                              矩形覆盖
N个不同的颜色的不透明的长方形(1 <= N <= 1000)被放置在一张宽为A长为B的白纸上。
这些长方形被放置时，保证了它们的边于白纸的边缘平行。
所有的长方形都放置在白纸内，所以我们会看到不同形状的各种颜色。
坐标系统的原点(0,0)设在这张白纸的左下角，而坐标轴则平行于边缘。

输入格式：
每行输入的是放置长方形的方法。
第一行输入的是那个放在底的长方形(即白纸)。

第 1 行: A ， B 和 N, 由空格分开 (1 <=A, B<=10,000)
第 2 到N+1行: 为五个整数　llx, lly, urx, ury, color　这是一个长方形的左下角坐标，右上角坐标和颜色(1<=color<=2500)。
颜色 1和底部白纸的颜色相同。

输入样例：
20 20 3
2 2 18 18 2
0 8 19 19 3
8 0 10 19 4

输出格式：
输出文件应该包含一个所有能被看到颜色连同该颜色的总面积的清单( 即使颜色的区域不是连续的)，按color的增序顺序。
不要显示没有区域的颜色。

输出样例：
1 91
2 84
3 187
4 38



地主 发表时间: 04-08-02 23:22
回复: dyx [dyx]   论坛用户   登录
哎~~~~~

B1层 发表时间: 04-08-10 20:56
回复: kert_t8 [kert_t8]   论坛用户   登录
有没有人讲一讲啊？

B2层 发表时间: 04-08-15 09:46
回复: dyx [dyx]   论坛用户   登录
哎~~~~~我已经做出这道题了。。。但难道真的要我把代码发出来！？20CN真的就没有真正的编程高手吗？。。。如果明天你们还不知道怎么做，那我就把代码发出来，如果有必要，我也可以给你们讲解。。。

B3层 发表时间: 04-08-28 17:31
回复: dyx [dyx]   论坛用户   登录
对了，我再给大家提示一下，但只提示两个字：离散

B4层 发表时间: 04-08-28 17:33
回复: dyx [dyx]   论坛用户   登录
................

B5层 发表时间: 04-08-29 15:40
回复: dyx [dyx]   论坛用户   登录
type jx=record
    color:integer;
    llx:integer;
    lly:integer;
    urx:integer;
    ury:integer;
end;
var
  bz:array[0..5000] of jx;
  x:array[1..5000] of longint;
  y:array[1..5000] of longint;
  z:array[1..5000] of longint;
  a,b,n,i,j,t,k:longint;
procedure inin;
begin
    fillchar(z,sizeof(z),0);
    read(a,b,n);
    j:=0;
    bz[0].llx:=0;
    bz[0].lly:=0;
    bz[0].urx:=a;
    bz[0].ury:=b;
    bz[0].color:=1;
    for i:=1 to n do
        begin
            read(bz[i].llx,bz[i].lly,bz[i].urx,bz[i].ury,bz[i].color);
            inc(j);
            x[j]:=bz[i].llx;
            y[j]:=bz[i].lly;
            inc(j);
            x[j]:=bz[i].urx;
            y[j]:=bz[i].ury;
        end;
    x[j+1]:=bz[0].llx;
    x[j+2]:=bz[0].urx;
    y[j+1]:=bz[0].lly;
    y[j+2]:=bz[0].ury;
end;
procedure px;
begin
    for i:=0 to n*2+1 do
        for j:=i+1 to n*2+2 do
            begin
                if x[i]>x[j] then
                    begin
                        t:=x[i];
                        x[i]:=x[j];
                        x[j]:=t;
                    end;
                if y[i]>y[j] then
                    begin
                        t:=y[i];
                        y[i]:=y[j];
                        y[j]:=t;
                    end;
            end;
end;
procedure cheke(llx,lly,urx,ury:integer);
begin
  for k:=n downto 0 do
    if (llx>=bz[k].llx)and(lly>=bz[k].lly)and(urx<=bz[k].urx)and(ury<=bz[k].ury)
    then begin
          z[bz[k].color]:=z[bz[k].color]+abs(llx-urx)*abs(lly-ury);
          exit;
        end;
end;

procedure main;
begin
    for i:=1 to n*2+2-1 do
        for j:=1 to n*2+2-1 do
                    cheke(x[i],y[j],x[i+1],y[j+1]);
end;
procedure out;
begin
        for i:=1 to 2500 do
        if z[i]>0 then
            begin
                write(i,' ',z[i]);
                writeln;
            end;
end;
begin
    inin;
    px;
    main;
    out;
end.

B6层 发表时间: 04-08-29 15:44
回复: dyx [dyx]   论坛用户   登录
以上程序通过Turbo Pascal、Borland Pascal、Free Pascal For DOS编译，并正常运行，通过USACO的全部测试数据。需要测试数据的加我QQ:341152902

B7层 发表时间: 04-08-29 16:03

论坛: 编程破解

20CN网络安全小组版权所有
Copyright © 2000-2010 20CN Security Group. All Rights Reserved.
论坛程序编写：NetDemon

粤ICP备05087286号