//
you're reading...
Bài tập huấn luyện, Chủ đề đồ thị (Graph)

Bài tập huấn luyện: Xếp các hình chữ nhật

[Bộ đề huấn luyện về chủ đề đồ thị]


Chuyên đề Đồ thị (Graph) – Bài 17


Đề bài


Cho một tờ giấy hình chữ nhật có màu trắng có các cạnh là A và B nguyên dương, A là cạnh dọc, B là cạnh ngang. A, B£60. Ta lâlfn lượt đặt lên tờ giấy N hình chữ nhật có các  màu nói chung là khác nhau, mỗi hình chữ nhật này đều nằm bên trong tờ giấy. Các màu đánh số từ 1 đến 64, màu trắng đánh số là 1.

Các hình chữ nhật đều có cạnh song song với các cạnh của tờ giấy và được định vị như sau: dùng hệ trục toạ độ có gốc là tâm tờ giấy và các trục toạ độ song song với các cạnh tờ giấy. Khi đó mỗi hình chữ nhật sẽ được cho bởi 5 số nguyên x, y, z, t, m trong đó (x,y) là toạ độ đỉnh trái dưới, (z,t) là tạo đỉnh phải trên, M là số hiệu màu.

Sau khi đặt N hình chữ nhật, trên nền tờ giấy ta sẽ nhìn thấy các mảng màu khác nhau.

Một hình H là một tập hợp các mảng cùng màu thoả mãn điều kiện:

  1. Từ một điểm bất kỳ của H ta có thể đến một điểm bất kỳ khác của H bằng hai đường đi khác nhau nằm trong H (hai đường đi là khác nhau nếu chúng chỉ có hai điểm chung là điểm xuất phát và điểm kết thúc)
  2. Nếu thêm vào H một điểm khác thì điều kiện 1 không còn đựoc thoả mãn nữa

Cần tính diện tích các hình

Dữ liệu vào cho trong file CN.INP gồm một số nhóm dòng liên tiếp, mỗi nhóm là một tập dữ liệu của bài toán. Trong mỗi nhóm dòng, dòng thứ nhất ghi ba số A, B, N, tiếp theo là N dòng, mỗi dòng ghi 5 số x, y, z, t, m thể hiện một hình  chữ nhật. Các hình chữ nhật được đặt lên theo trình tự xuất hiện trong file.

Với mỗi tập dữ liệu đọc được ghi ra file CN.OUT một nhóm dòng: dòng thứ nhất ghi K là số hình, tiếp theo là K dòng, mỗi dòng ghi hai số U V với ý nghĩa hình màu U có diện tích V, hình màu nhỏ hơn ghi trước, nếu hai hình cùng màu, hình có diện tích nhỏ hơn ghi trước.

Ví dụ:

CN.INP CN.OUT
13 21 5

-7 -5 -3 -1 4

-5 -3 5 3 2

-4 -2 -2 2 4

2 -2 3 -1 12

3 1 7 5 1

30 30 2

0 0 5 14 2

-10 –7 0 13 15

5

1 205

2 47

4 8

4 12

12 1

1 630

2 70

15 200

 


Hướng dẫn


[]


Chương trình


{$A+,B-,D+,E+,F-,G-,I+,L+,N+,O-,P-,Q-,R-,S+,T-,V+,X+}
{$M 16384,0,655360}

uses crt;

const
   tfi                  =       'CN.INP';
   tfo                  =       'CN.OUT';
   dx                   :       array[1..4] of integer=(1,0,-1,0);
   dy                   :       array[1..4] of integer=(0,1,0,-1);

var
   fi,fo                :       text;
   Doc,Ngang            :       integer;
   N                    :       integer;
   a                    :       array[-30..30,-30..30] of integer;
   xmax,xmin,ymax,ymin  :       integer;
   LT                   :       array[-30..30,-30..30] of integer;
   slt                  :       integer;
   color                :       array[1..3600] of integer;
   S                    :       array[1..3600] of real;
   Q                    :       array[1..3600,1..2] of integer;
   qf,ql                :       integer;



procedure Sinhdl;
var ch: char;
    i: integer;
    x1,y1,x2,y2,mau: integer;
begin
   clrscr;
   writeln('Ban co tao file ',tfi,' (C/K)?');
   repeat ch:=readkey until upcase(ch) in ['C','K'];
   if upcase(ch)='K' then exit;
   randomize;
   assign(fi,tfi); rewrite(fi);
   for i:=1 to 10 do
      begin
         Doc:=random(55)+5;
         Ngang:=random(55)+5;
         xmax:=ngang div 2;
         ymax:=doc div 2;
         N:=random(100);
         writeln(fi,Ngang,' ',Doc,' ',N);
         for i:=1 to N do
            begin
               x1:=random(xmax)-xmax;
               y1:=random(ymax)-ymax;
               x2:=x1+random(xmax-x1);
               y2:=y1+random(ymax-y1);
               mau:=random(4)+1;
               writeln(fi,x1,' ',y1,' ',x2,' ',y2,' ',mau);
            end;
      end;
   close(fi);
end;

procedure InitQ;
begin
   qf:=1;
   ql:=1;
end;
procedure Put(u,v: integer);
begin
   q[ql,1]:=u;
   q[ql,2]:=v;
   inc(ql);
end;
procedure Get(var u,v: integer);
begin
   u:=q[qf,1];
   v:=q[qf,2];
   inc(qf);
end;
function Qempty: boolean;
begin
   Qempty:=(qf=ql);
end;

procedure Docdl;
var i,j: integer;
    x1,y1,x2,y2,mau,u,v: integer;
begin
   readln(fi,Doc,Ngang,N);
   for i:=-30 to 30 do
      for j:=-30 to 30 do a[i,j]:=1;
   for i:=1 to N do
      begin
         readln(fi,x1,y1,x2,y2,mau);
         for u:=x1 to x2-1 do
            for v:=y1 to y2-1 do
               a[u,v]:=mau;
      end;
   xmin:=-(ngang+1) div 2;
   ymin:=-(doc+1) div 2;
   xmax:= (ngang+1) div 2;
   ymax:= (doc+1) div 2;
end;

function Inside(u,v: integer): boolean;
begin
   Inside:=(u>=xmin) and (u<=xmax-1) and (v>=ymin) and (v<=ymax-1); end; function dt(u,v: integer): real; var cx,cy: real; begin    if ((u>xmin) and (u<xmax-1)) or       ((u=xmin) and (u=-ngang div 2)) or       ((u=xmax-1) and (u=ngang div 2-1)) then cx:=1.0 else cx:=0.5;    if ((v>ymin) and (v<ymax-1)) or       ((v=ymin) and (v=-doc div 2)) or       ((v=ymax-1) and (v=doc div 2-1)) then cy:=1.0 else cy:=0.5;       dt:=cx*cy; end; procedure DuyetCR(u,v: integer); var k,uu,vv: integer; begin    InitQ;    Put(u,v);    LT[u,v]:=slt;    S[slt]:=S[slt]+dt(u,v);    repeat       Get(u,v);       for k:=1 to 4 do          begin             uu:=u+dx[k]; vv:=v+dy[k];             if Inside(uu,vv) and (a[uu,vv]=a[u,v]) and (LT[uu,vv]=0) then                begin                   Put(uu,vv);                   S[slt]:=S[slt]+dt(uu,vv);                   LT[uu,vv]:=slt;                end;          end;    until Qempty; end; procedure Tinh; var u,v: integer; begin    Fillchar(LT,sizeof(LT),0);    slt:=0;    for u:=xmin to xmax-1 do       for v:=ymin to ymax-1 do          if LT[u,v]=0 then             begin                inc(slt);                color[slt]:=a[u,v];                S[slt]:=0;                DuyetCR(u,v);             end; end; procedure DoiChoI(var u,v: integer); var tg: integer; begin    tg:=u;    u:=v;    v:=tg; end; procedure DoiChoR(var u,v: real); var tg: real; begin    tg:=u;    u:=v;    v:=tg; end; procedure Sort; var i,j: integer; begin    for i:=1 to slt-1 do       for j:=i+1 to slt do          if (color[i]>color[j]) or
            ((color[i]=color[j]) and (S[i]>S[j])) then
               begin
                  DoiChoI(color[i],color[j]);
                  DoiChoR(S[i],S[j]);
               end;
end;

procedure Inkq;
var i: integer;
begin
   writeln(fo,slt);
   for i:=1 to slt do
      writeln(fo,color[i],' ',S[i]:0:0);
end;

BEGIN
   {Sinhdl;}
   assign(fi,tfi); reset(fi);
   assign(fo,tfo); rewrite(fo);
   while not seekeof(fi) do
      begin
         Docdl;
         Tinh;
         Sort;
         Inkq;
      end;
   close(fi); close(fo);
END.
Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười Hai 2016
H B T N S B C
« Th11   Th1 »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

Thống kê

  • 149,868 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: