Quét Graham và hệ điều hành Jarvis
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (104.38 KB, 4 trang )
Bao lồi với thuật toán Quét Graham và Diễu hành Jarvis (Bọc gói)
Nguyễn Thế Anh
I. Bài toán
Bao lồi của 1 tập hợp Q gồm các điểm của đa giác lồi nhỏ nhất P mà mỗi điểm của Q nằm
trên biên của P hoặc trong phần trong của nó. Hay có thể phát biểu thành bài toán như sau:
Cho n điểm A1(x1,y1), A2(x2,y2),..., An(xn,yn). Hãy tìm đa giác lồi có diện tích nhỏ nhất
chứa tất cả các điểm trên. Đa giác như vậy gọi là bao lồi của n điểm đã cho.
Rõ ràng bao lồi cần tìm có các đỉnh thuộc các điểm đã cho.
II. Các phương pháp giải
A. Thuật toán quét Graham
1. Phát biểu thuật toán
+ Trong các điểm có tung độ nhỏ nhất, tìm điểm có hoành độ lớn nhất, gọi điểm này là B
1
.
Điểm này chắc chắn thuộc bao, đổi vị trí điểm này với A
1
.
+ Kết nạp thêm các điểm A
2
,A
3
vào bao
+ Với mỗi điểm A
i
(i=1..n) tính các góc giữa véctơ A
1
A
i
với đường thẳng nằm ngang. Sắp
xếp lại các điểm theo thứ tự tăng dần của các góc này
+ Với mỗi điểm A
i
.(i=1..n) kiểm tra thuộc bao trước đó có cònthuộc bao hay không, nếu
không thì loại bỏ. Kết nạp điểm A
i
vào bao.
Tiếp tục quá trình cho đến hết.
2. Đoạn chương trình
program baoloigrama;
uses crt;
type p=record
x,y:longint;
end;
var
m,n:byte;
A,B:array[byte] of p;
procedure input;
var i:byte; f:text; s:string;
begin
clrscr; write('Ten file du lieu vao : ');
readln(s); assign(f,s); {$I-} reset(f); {$I+} readln(f,n);
for i:=1 to n do readln(f,A[i].x,A[i].y); close(f);
End;
function goc(m1,m2:p):real;
var dx,dy:longint; t:real;
begin
dx:=m2.x-m1.x; dy:=m2.y-m1.y;
if (dx=0) and (dy=0) then t:=0
else t:=dy/(abs(dx)+abs(dy));
if dx<0 then t:=2-t
else
if dy<0 then t:=4+t; goc:=t*90;
end;
functiondirect(m1,m2,m3:P):integer;
var dx1,dx2,dy1,dy2:longint;
begin
dx1:=m2.x-m1.x;dy1:=m2.y-m1.y;
dx2:=m3.x-m1.x;dy2:=m3.y-m1.y;
if dy2*dx1-dy1*dx2>0 thendirect:=1;
if dy2*dx1-dy1*dx2<0 thendirect:=-1;
if dy2*dx1-dy1*dx2=0 then
begin
if (dx1*dx2<0) or (dy1*dy2<0) then direct:=1
else
if (dx1*dx1+dy1*dy1)>= (dx2*dx2+dy2*dy2) then direct:=0
else direct:=1;
end;end;
procedure Swap;
var i,j:byte; t:real; q:p;g:array[byte]of real;
begin
for i:=2 to n do g[i]:=goc(a[1],a[i]);
for i:=2 to n-1 do
for j:=i+1 to n do
if g[i]>g[j] then
begin
t:=g[i]; g[i]:=g[j];g[j]:=t;
q:=a[i]; a[i]:=a[j];a[j]:=q;
end;
end;
procedure graham;
var i,min:byte; q:p; t:real;
begin
min:=1;
for i:=2 to n do
if a[i].yfor i:=1 to n do
if a[i].y=a[min].y then
if a[i].x>a[min].x then min:=1;
q:=a[1]; a[1]:=a[min]; a[min]:=q; soft;
b[0]:=a[n]; m:=3;
for i:=1 to 3 do b[i]:=a[i];
for i:=4 to n do
begin
while direct(b[m-1],b[m],a[i])<=0 do m:=m-1;
m:=m+1; b[m]:=a[i];end;
end;end;
BEGIN
input;graham;
END.
B.Thuật toán 'Diễu hành Jarvis'(Bọc gói)
1. Phát biểu thuật toán
+ Chọn điểm thứ nhất là điểm có tung độ bé nhất, gọi là điểm B
1
. Điểm này chắc chắn
thuộc bao lồi. Đặt B
n+1
= B
1
.
+ Dùng 1 tia quan điểm B
1
quét ngược chiều kim đồng hồ cho đến khi gặp 1 điểm khác.
Gọi điểm này là B
2
+ Dùng 1 tia quan điểm B
2
quét ngược chiều kim đồng hồ cho đến khi gặp 1 điểm khác.
Gọi điểm này là B
3
+ Lặp lại quá trình trên cho đến khi điểm chọn trùng lại điểm B
n+1
Ta có thể nhận thấy không cần quét tất cả các góc có thể. Góc cần quét chắc chắn lớn hơn
hay bằng góc đã quét được trước đó. Đồng thời các điểm được chọn cần đánh đấu để
không được chọn lại lần sau.
2. Đoạn chương trình
Về chương trình thì chỉ cần thay thủ tục javis sau vào thủ tục Graham ở chương trình trên
procedure Javis;
var i,j:byte;
min,g:real;
C:array[byte]of boolean;
begin
for j:=1 to n do c[j]:=true; i:=1;
for j:=2 to n do ifa[j].yrepeat
m:=m+1; B[m]:=A[i];C[i]:=false;
i:=n+1; g:=min;min:=360;
for j:=1 to n+1 do
if c[j] then
if ( goc(b[m], a[j])>g) and (goc(b[m], a[j])
begin i:=j;min:=goc(b[m],a[i]);end;
until i=n+1;
writeln('So ding thuoc bao la : ',m); readln;
end;
Ngoài ra, nếu bạn muốn vẽbao lồi ra màn hình thì chỉ cần thêm thủ tục vẽ sau vao chương
trình
procedure ve;
var gd, gm:integer;
i:byte;
s:string[3];
begin
gd:=0;
initgraph(gd,gm,'C:tp7bgí);
b[m+1]:=b[1];
for i:=1 to n do
begin
putpixel(a[i].x,a[i].y,white);
str(i,s);
outtextxy(a[i].x,a[i].y+5,s);
end;
for i:=1 to m do line(b[i].x,b[i].y,b[i+1].x,b[i+1].y);
readln;
closegraph;
end;
ở chương trình chính bạn gọi các thủ tục như sau :
BEGIN
nhap;
graham;{hoặc Javis}
VE;
END.
III. Các bài toán
Sau khi tham khảo hai thuật toán trên, mời bạn thử sức với các bài toán sau :
1. Cho n điểm , hãy tìmtrong n điểm này ba điểm tạo thành 1 tam giác mà số lượng điểm
nằm trong đó (kể cả biên) là lớn nhất.
2.Rào cây
Người ta muốn rào các cây ở một khu vườn để bảo vệ. Hàng rào được tạo bởi một đường
gấp khúc đơn khép kín có đỉnh là một số cây làm cột mốc, sao cho các cây khác phải nằm
trong hàng rào (một số cây có thể nằm trên biên).
Hãy xác định một phương án rào cây sao cho số cây phải làm cột mốc là ít nhất.
Dữ liệu vào : - Tệp văn bản Cay.inp, dòng đầu là số cây, các dòng tiếp là toạ độ của các
cây. Các cây được đánh số từ 1 theo thứ tự trong file.
Dữ liệu ra : - Ghi ra file văn bản Cay.out, dòng đầu là số cây làm cột mốc, dòng sau là số
hiệu các cây này theo đúng thứ tự tạo hàng rào.
Giới hạn: Số cây ≤255
Vdụ :
