Bài toán chia đất

**chopes** · 07-12-2008 17:53

Mọi người giúp mình bài này với. Chủ yếu là làm ntn với bộ test lớn thôi.
Một người nông dân có moọt thửa ruộng hình chữ nhật kích thước N*M, phân chia ruộng cho K người con, đánh số từ 1 đến K.
Việc phân chia thực hiện như sau: thửa ruộng được phân thành từng ô vuông có cạnh bằng 1 đơn vị. Ban đầu mỗi người con được nhận trước một ô vuông, ko có trường hợp 2 người nhận chung một ô. Sau đó ở mỗi lượt, lần lượt mỗi người con theo số hiệu từ nhỏ đến lớn, nhận tiếp các ô vuông chưa có ai nhận và kề cạnh với môt trong các ô vuông thuộc sở hữu của mình từ các lượt trước đó. Giả sử, đến lượt thứ K, người con thứ i nhận thêm các ô vuông kề cạnh với các ô vuông đã nhận ở lượt thứ K-1, sau khi nhận xong, người con thu i+1 đến nhận ... Quá trình lặp lại cho đến khi tất cả các ô đều được nhận.
YÊU CẦU : Xác định diện tích được nhận của mỗi người con.
Dữ liệu vào: Chiadat.inp
_Dòng đầu 3 số nguyên n,m,k
_K dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương. Dòng thứ i trong K dòng chỉ vị trí dòng cột của ô mà người con thứ i nhận ban đầu.
Dũ liệu ra: Chiadat.out
_K số, số thứ i là diện tích mà người con thứ i nhận được.
(N,M<=1000, 2<=K<=5)
VD:
Chiadat.inp
500 500 5
29 356
425 259
149 500
412 6
386 224
Chiadat.out
67734 38102 34234 44162 65768
chiadat.inp
10 10 3
1 1
9 4
5 6
Chiadat.out
16 38 46

**chooco_pie** · 07-12-2008 19:08

mình có một bài tập đồ họa về pascal như vậy muốn đưa lên cho mọi người cùng xem:
PROGRAM CUONGTINB2K6;
USES CRT,GRAPH;
VAR GM,GD,CO,KIEU,X,Y:INTEGER;
I:INTEGER;
COS1,SIN1,GOC,ALPHA,ALPH,COS2,SIN2:REAL;
ALPHA1,COS3,SIN3:REAL;
PROCEDURE CIRCLEPOINT8(XC,YC,X,Y:INTEGER;C:WORD);
BEGIN
PUTPIXEL(XC+X,YC+Y,C);
PUTPIXEL(XC+Y,YC+X,C);
PUTPIXEL(XC-X,YC-Y,C);
PUTPIXEL(XC+Y,YC-X,C);
PUTPIXEL(XC+X,YC-Y,C);
PUTPIXEL(XC-Y,YC-X,C);
PUTPIXEL(XC-Y,YC+X,C);
PUTPIXEL(XC-X,YC+Y,C);
END;
procedure linedda(x1,y1,x2,y2:integer;c:word);
var x,dx,dy:integer;
y,m:real;
begin
dx:=x2-x1;
dy:=y2-y1;

m:=dy/dx;
x:=x1;
y:=y1;
putpixel(x,round(y),c);
while x<x2 do
begin
x:=x+1;
y:=y+m;
putpixel(x,round(y),c);
end;
end;
procedure lineddaY(x1,y1,x2,y2:integer;c:word);
var Y,dx,dy:integer;
X,m:real;
begin
dx:=x2-x1;
dy:=y2-y1;
m:=dx/dy;
x:=x1;
y:=y1;
putpixel(ROUND(x),y,c);
while Y<Y2 do
begin
x:=x+M;
y:=y+1;
putpixel(ROUND(x),Y,c);
end;
end;
PROCEDURE BOUNDARYFILL(X,Y,FILLCOLOR,BOUNDARYCOLOR:INTEGER);
VAR PRESENTCOLOR:INTEGER;
BEGIN
PRESENTCOLOR:=GETPIXEL(X,Y);
IF (PRESENTCOLOR<> BOUNDARYCOLOR) AND (PRESENTCOLOR<>FILLCOLOR)THEN
BEGIN
PUTPIXEL(X,Y,FILLCOLOR);
BOUNDARYFILL(X+1,Y,FILLCOLOR,BOUNDARYCOLOR);
BOUNDARYFILL(X-1,Y,FILLCOLOR,BOUNDARYCOLOR);
BOUNDARYFILL(X,Y+1,FILLCOLOR,BOUNDARYCOLOR);
BOUNDARYFILL(X,Y-1,FILLCOLOR,BOUNDARYCOLOR);
BOUNDARYFILL(X-1,Y-1,FILLCOLOR,BOUNDARYCOLOR);
BOUNDARYFILL(X-1,Y+1,FILLCOLOR,BOUNDARYCOLOR);
BOUNDARYFILL(X+1,Y-1,FILLCOLOR,BOUNDARYCOLOR);
BOUNDARYFILL(X+1,Y+1,FILLCOLOR,BOUNDARYCOLOR);
END;
END;
PROCEDURE drawcircle(xc,yc,R:INTEGER;C:WORD);
VAR X,Y:INTEGER;P:REAL;
BEGIN
P:=5/4-R;
X:=0; Y:=R;
CIRCLEPOINT8(XC,YC,X,Y,C);
WHILE X<Y DO
BEGIN
IF P<0 THEN P:= P+2*X +3
ELSE
BEGIN
Y:=Y -1;
P:=P +2*(X-Y) +5;
END;
X:= X+1;
CIRCLEPOINT8(XC,YC,X,Y,C);
END;
END;
BEGIN
CLRSCR;
GD:=DETECT;
INITGRAPH(GD,GM,'D:\BP7\BGI');
IF GRAPHRESULT <> 0 THEN
BEGIN
WRITE ('LOI DO HOA');
DELAY(100);
HALT;
END;
REPEAT
FOR I:=1 TO 180 DO
BEGIN
ALPHA:=6*I;
COS1:=COS(ALPHA);
SIN1:=SIN(ALPHA);
ALPH:=36*I;
COS2:=COS(ALPH);SIN2:=SIN(ALPH);
ALPHA1:=216*I;
COS3:=COS(ALPHA1); SIN3:=SIN(ALPHA1);
{mat troi}
DRAWCIRCLE(100,180-I,20,14);
SETFILLSTYLE(1,15);
FLOODFILL(100,180-I,14);

{MO DAT}
ELLIPSE(680,480,0,360,340,160);

{CAY}{ ELLIPSE(590,280,0,360,20,40); }

LINEDDAY(580,300,580,360,10);
LINEDDAY(600,300,600,360,10);
LINEDDA(580,360,600,360,10);
LINEDDA(540,240,580,240,10);
LINEDDA(600,240,640,240,10);
LINEDDA(540,300,580,240,10);
LINEDDA(600,240,640,300,10);
LINEDDA(540,300,580,300,10);
LINEDDA(600,300,640,300,10);
LINEDDA(540,240,590,160,10);
LINEDDA(590,160,640,240,10);
{NGUOI 1}
LINEDDAY(540,400,540,420,15);
LINEDDAY(550,400,550,420,15);
LINEDDA(540,400,550,400,15);
LINEDDA(540,420,550,420,15);
LINEDDA(520,420,530,410,15);
LINEDDA(520,425,530,415,15);
LINEDDA(530,410,540,420,15);
LINEDDA(530,415,540,420,15);
DRAWCIRCLE(545,393,6,15);
LINEDDA(530,385,540,400,15);
LINEDDA(550,400,560,420,15);

{NGUOI2} LINEDDA(565,430,585,430,15);
LINEDDA(565,440,585,440,15);
LINEDDAY(565,430,565,440,15);
linedday(585,430,585,440,15);
DRAWCIRCLE(591,435,6,15);
LINEDDA(560,420,585,430,15);
LINEDDA(565,450,585,440,15);
LINEDDA(540,435,550,425,15);
LINEDDA(550,425,565,432,15);
LINEDDA(550,430,565,435,15);
LINEDDA(545,440,550,430,15);

{nui}
LINEDDA(40,220,85,165,1);
LINEDDA(85,165,110,140,1);
LINEDDA(110,140,135,120,1);
LINEDDA(135,120,150,110,1);
LINEDDA(150,110,170,105,1);
LINEDDA(170,105,180,105,1);
LINEDDA(180,105,195,120,1);
LINEDDAY(195,120,195,130,1);
LINEDDA(155,220,170,175,1);
LINEDDA(170,175,195,130,1);
LINEDDA(195,130,210,105,1);
LINEDDA(210,105,240,80,1);
LINEDDA(240,80,260,70,1);
LINEDDA(260,70,280,75,1);
LINEDDA(280,75,310,95,1);
LINEDDA(310,95,320,110,1);
LINEDDA(320,110,340,140,1);
LINEDDA(340,140,385,220,1);
LINEDDA(340,140,385,100,1);
LINEDDA(385,100,400,85,1);
LINEDDA(400,85,430,75,1);
LINEDDA(430,75,450,80,1);
LINEDDA(450,80,460,100,1);
LINEDDA(460,100,480,150,1);
LINEDDA(480,150,500,220,1);
LINEDDA(480,150,490,135,1);
LINEDDA(490,135,520,120,1);
LINEDDA(520,120,550,120,1);
LINEDDA(550,120,665,220,1);
LINEDDA(320,110,340,80,1);
LINEDDA(340,80,385,65,1);
LINEDDA(385,65,395,70,1);
LINEDDA(395,70,400,85,1);
{ setfillstyle(1,1);
floodfill(340,100,1);
{CACH CO1}

LINEDDA(20,30,30,25,15);
LINEDDA(30,25,40,30,15);
LINEDDA(40,30,50,25,15);
LINEDDA(50,25,60,30,15);
LINEDDA(35,30,45,30,15);

{CANH CO 2} LINEDDA(30,50,45,45,15);
LINEDDA(45,45,55,50,15);
LINEDDA(55,50,70,45,15);
LINEDDA(70,45,80,50,15);
LINEDDA(50,50,62,50,15);
{ca}
LINEDDA(435-I,270,468-I,250,14);
LINEDDA(435-I,270,470-I,290,14);
LINEDDA(458-I,256,490-I,280,14);
LINEDDA(459-I,284,490-I,260,14);
LINEDDAY(490-I,260,490-I,280,14);
DRAWCIRCLE(449-I,270,1,14);
setfillstyle(9,14);
floodfill(460-i,270,14);
setfillstyle(9,14);
floodfill(485-i,270,14);

{thuyen} setlinestyle(0,0,3);
ellipse(80+i,320,0,360,10,15);
ellipse(140+i,320,0,360,10,15);
ellipse(110+i,325,180,360,70,15);
ellipse(110+i,325,180,360,70,30);
linedday(70+i,260,70+i,335,15);
lineDDA(40+i,323,70+i,260,15);
lineDDAY(150+i,260,150+I,336,15);
lineDDA(70+I,260,100+I,305,15);
lineDDA(150+I,260,120+I,305,15);
line(80+I,305,140+I,305);
lineDDA(120+I,305,150+I,260,15);
LINEDDA(150+I,260,180+I,322,15);
{ setfillstyle(9,15);
floodfill(80+I,320,15);
setfillstyle(8,15);
floodfill(110+I,340+I,15); }
{NUOC}
LINEDDA(60,245,110,245,15);
LINEDDA(20,360,50,360,15);
LINEDDA(160,250,200,250,15);
LINEDDA(270,375,100,375,15);
LINEDDA(130,380,170,380,15);
LINEDDA(200,300,240,300,15);
LINEDDA(10,280,50,280,15);
LINEDDA(10,310,30,310,15);
LINEDDA(60,360,70,360,15);
LINEDDA(170,345,200,345,15);
LINEDDA(260,260,300,260,15);
LINEDDA(200,280,240,280,15);
LINEDDA(250,290,280,290,15);
LINEDDA(330,240,380,240,15);
LINEDDA(90,270,130,270,15);
LINEDDA(100,290,130,290,15);
LINEDDA(90,320,130,320,15);
LINEDDA(220,320,270,320,15);
LINEDDA(320,280,360,280,15);
LINEDDA(350,260,380,260,15);
LINEDDA(240,380,280,380,15);
LINEDDA(300,360,330,360,15);
LINEDDA(380,360,420,360,15);
LINEDDA(440,360,460,360,15);
LINEDDA(500,260,540,260,15);
LINEDDA(480,300,520,300,15);
LINEDDA(400,270,440,270,15);
LINEDDA(420,320,460,320,15);
LINEDDA(480,300,520,300,15);
LINEDDA(340,370,400,370,15);
LINEDDA(280,340,320,340,15);
LINEDDA(340,320,380,320,15);
LINEDDA(300,305,340,305,15);
LINEDDA(400,310,440,310,15);
LINEDDA(400,240,470,240,15);
{ CON DUONG}
LINEDDA(10,470,340,470,3);
LINEDDA(10,400,340,400,3);
LINEDDAY(10,400,10,470,3);
LINEDDAY(340,400,340,470,3);

{O TO}
LINEDDA(60,410,140,410,14);
LINEDDA(140,410,180,440,14);
LINEDDA(20,440,60,410,14);
LINEDDAY(20,440,20,460,14);
LINEDDA(20,460,65,460,14);
LINEDDA(180,440,200,440,14);
LINEDDAY(200,440,200,460,14);
LINEDDA(150,460,200,460,14);
LINEDDA(90,460,120,460,14);
LINEDDA(110,420,140,420,14);
LINEDDAY(110,420,110,440,14);
LINEDDA(110,440,160,440,14);
LINEDDA(140,420,160,440,14);
LINEDDAY(90,420,90,440,14);
LINEDDA(50,440,70,420,14);
LINEDDA(70,420,90,420,14);
LINEDDA(50,440,90,440,14);
DRAWCIRCLE(78,460,11,14);
DRAWCIRCLE(135,460,11,14);
{ SETFILLSTYLE(1,15);
FLOODFILL(78,460,15);
{SAO}
SETCOLOR(RANDOM(15));
OUTTEXTXY(640,140,'*');
OUTTEXTXY(660,100,'*');
OUTTEXTXY(570,90,'*');
OUTTEXTXY(600,120,'*');
OUTTEXTXY(540,100,'*');
OUTTEXTXY(100,20,'*');
OUTTEXTXY(120,60,'*');
OUTTEXTXY(150,30,'*');
OUTTEXTXY(180,20,'*');
OUTTEXTXY(200,40,'*');
OUTTEXTXY(230,30,'*');
OUTTEXTXY(260,20,'*');
OUTTEXTXY(300,40,'*');
OUTTEXTXY(320,10,'*');
OUTTEXTXY(380,40,'*');
OUTTEXTXY(400,20,'*');
OUTTEXTXY(420,40,'*');
OUTTEXTXY(440,60,'*');
OUTTEXTXY(460,20,'*');
OUTTEXTXY(490,80,'*');
OUTTEXTXY(500,10,'*');
OUTTEXTXY(520,20,'*');
OUTTEXTXY(540,50,'*');
OUTTEXTXY(560,20,'*');
OUTTEXTXY(580,40,'*');
OUTTEXTXY(590,30,'*');
OUTTEXTXY(600,60,'*');
OUTTEXTXY(620,50,'*');
OUTTEXTXY(640,10,'*');
OUTTEXTXY(660,40,'*');
OUTTEXTXY(680,10,'*');
OUTTEXTXY(565,390,'*');
OUTTEXTXY(580,375,'*');
OUTTEXTXY(600,375,'*');
OUTTEXTXY(610,390,'*');
OUTTEXTXY(610,400,'*');
OUTTEXTXY(610,420,'*');
OUTTEXTXY(610,420,'*');
OUTTEXTXY(605,430,'*');
OUTTEXTXY(600,440,'*');
OUTTEXTXY(590,450,'*');
OUTTEXTXY(575,465,'*');
OUTTEXTXY(555,375,'*');
OUTTEXTXY(540,375,'*');
OUTTEXTXY(520,380,'*');
OUTTEXTXY(515,390,'*');
OUTTEXTXY(525,430,'*');
OUTTEXTXY(515,400,'*');
OUTTEXTXY(550,470,'*');
OUTTEXTXY(520,420,'*');
OUTTEXTXY(545,455,'*');
OUTTEXTXY(535,445,'*');
OUTTEXTXY(555,475,'*');
OUTTEXTXY(350,460,'NGUYEN DUC CUONG');

SETTEXTSTYLE(4,0,1);
DELAY(50);
CLEARDEVICE;
END;
UNTIL KEYPRESSED;
CLOSEGRAPH;
READLN;
END.
Ai có bài nào khá hơn thế này không , hi vọng post code lên cho mình tham khảo nha..