Hình trong tin!

Tác giả: Đỗ Mạnh Dũng

Hình học đối với giác quan của con người thì khá quen thuộc và dễ dàng. Nhưng hình học đối với máy tính thì lại là một vấn đề khác. Nhiếu bài toán ta có thể giải ngay lập tức bằng cách “nhìn vào hình vẽ ta thấy”, nhưng để thể hiện trên máy tính thì cần những chương trình không đơn giản chút nào.

Các giải thuật hình học thường là các giải thuật đẹp và đôi khi là rất bất ngờ. Thực vậy, những tưởng có những bài toán ta phải giải quyết với chi phí thuật toán rất lớn (đôi khi không thể chấp nhận được), nhưng nhờ vào chính những tính chất đặc biệt của hình học mà ta lại có thể giải quyết nó một cách dễ dàng và “đẹp mắt”.
I. Biểu diễn hình học trên máy tính.

Đây không phải là một vấn đề khó khăn. Nhưng ta nên có một cách biểu diễn thống nhất cho riêng mình, như vậy sẽ dễ dàng trong việc thể hiện thuật toán. Thông thường người ta có cách biểu diễn như sau:

Điểm:

Point = record

x, y: Real;

end;

Đường thẳng:

Line = Record

p1, p2: Point;

end;

Đa giác:

Polygon = array[1..n] of Point;

Để thuận lợi thì khi biểu diễn đa giác ta nên thêm hai đỉnh ở đầu và cuối: đỉnh 0 bằng đỉnh n và đỉnh n + 1 bằng đỉnh 1.

Từ đây ta cũng thống nhất với cách khai báo này cho các đoạn chương trình có thể dùng đến.

Chú ý: Ta dễ dàng nhận thấy rằng các phép toán thực hiện để giải quyết bài toán hình học thì hầu hết là phải làm việc với số thực. Vì vậy ta cũng cần phải chú ý một số mẹo nhỏ khi khai báo dữ liệu và biên dịch. Tuỳ vào kích thước và yêu cầu về độ chính xác của kết quả bài toán ta phải có những chọn lựa hợp lý. Bảng dưới đây là những kiểu số thực mà Pascal có sẵn:

Kiểu


Giới hạn


Chữ số có nghĩa


Kích thước (Byte)

Single


1.5e-45..3.4e38


7-8


4

Real


2.9e-39..1.7e38


11-12


6

Double


5.0e-324..1.7e308


15-16


8

Extended


3.4e-4932..1.1e4932


19-20


10



Đặc biệt, mặc dù chỉ khi ta dùng Double hoặc Extended ta mới phải khai báo biên dịch {$N+}, nhưng ta nên lúc nào cũng làm như vậy. Vì khi đó máy tính sẽ dùng bộ đồng xử lý toán học, các phép toán với số thực sẽ thực hiện nhanh chẳng kém gì so với số nguyên (thậm chí còn nhanh hơn nếu ta dùng kiểu số thực Double). Tốt nhất hãy dùng thử và tự so sánh, sẽ thấy ngay sự khác biệt.

Một điều nữa cùng cần chú ý là sai số trong tính toán. Làm việc với số thực bao giờ ta cũng phải chấp nhận với những sai số nhất định. Vì vậy khi so sánh hai giá trị với nhau ta chú ý không được dùng dấu “=”, mà phải xét trị tuyệt đối hiệu hai giá trị với một giá trị Epsilon nào đó. Ở đây, Epsilon là một số tương đối bé, tuỳ vào yêu cầu của bài toán mà ta có chọn lựa về giá trị của nó.

Ví dụ: Không được dùng: if x1 = x2 then …

mà phải dùng : if Abs(x1 – x2) < Eps then …



II. Các phương pháp hình học.

1. Điểm, đoạn thẳng - đường thẳng, diện tích đa giác.

a. Quan hệ giữa các điểm - hàm CCW.

Điều gợi nhớ ta nhất khi nhắc đến quan hệ giữa các điểm là khoảng cách giữa chúng. Ta có thể tính khoảng cách giữa hai điểm như sau:

function Dist(p1, p2: Point): Real;

begin

Dist := Sqrt(Sqr(p1.x – p2.x) + Sqr(p1.y – p2.y));

end;

Nhiều khi ta phải trả lời câu hỏi: “việc đi từ A, B sang C là ta đã rẻ phải hay rẽ trái?”. Điều này tưởng chừng như đơn giản và có cảm giác là vô nghĩa, nhưng thực tế nó lại rất quan trọng trong một số thuật toán cụ thể.

Rẽ phải Rẽ trái



Ta có thể dùng tích có hướng trong không gian để giải quyết vấn đề này. Ta đang làm việc trong không gian 2 chiều (mặt phẳng) vì vậy đối với chiều thứ 3 thì mọi giá trị đều là Zero (nếu ai hỏi tích có hướng là gì thì xin tham khảo ở chỗ khác).

Hàm CCW sau trả ra -1 nếu là rẽ trái, 1 nếu rẽ phải, 0 nếu 3 điểm thẳng hàng. Bạn đọc có thể xử lý cụ thể hơn trong trường hợp 3 điểm thẳng hàng (điểm nào nằm ở giữa), nhưng trong nhiều ứng dụng thì điều đó là không cấn thiết.

function CCW(p1, p2, p3: Point): Integer;

var

a1, b1, a2, b2, t: Real;

begin

a1 := p2.x – p1.x;

b1 := p2.y – p1.y;

a2 := p3.x – p2.x;

b2 := p3.y – p2.y;

t := a1*b2 – a2*b1;

if Abs(t) < Eps then CCW := 0

else

if t > 0 then CCW := 1

else CCW := -1;

end;

b. Đường thẳng, đoạn thẳng và giao của chúng.

Để biểu diễn đường thẳng ta có thể biểu diễn bằng toạ độ hai điểm trên đường thẳng đó. Nhưng đôi khi để tiện lợi cho tính toán, ta phải có được phương trình dưới dạng tổng quát của nó. Điều này là dễ dàng, bạn đọc có thể tham khảo thủ tục sau.

procedure Extract(p1, p2: Point; var a, b, c: Real);

begin

a := p1.y – p2.y;

b := p2.x – p1.x;

with p1 do c := -(a*x + b*y);

end;

Việc kiểm tra hai đoạn thẳng có cắt nhau không là cần thiết nhưng cũng không phải là một vấn đề khó. Hai đoạn thẳng cắt nhau khi hai đầu của đoạn này thì nằm về hai phía của đường thẳng chứa đoạn kia. Ta có thể dùng chính hàm CCW đã có. Nhưng cách làm thô thiển bình thường có vẻ còn tốt hơn:

function Intersect(l1, l2: Line): Boolean;

var

a1, b1, c1, a2, b2, c2, t1, t2: Real;

begin

Extract(l1.p1, l1.p2, a1, b1, c1);

Extract(l2.p1, l2.p2, a2, b2, c2);

with l1 do

t1 := (p1.x*a2+p1.y*b2+c2)*(p2.x*a2+p2.y*b2+c2);

with l2 do

t2 := (p1.x*a1+p1.y*b1+c1)*(p2.x*a1+p2.y*b1+c1);

Intersect := (t1 < Eps) and (t2 < Eps);

end;

Nếu ta muốn tính cụ thể toạ độ giao điểm của hai đường thẳng thì có lẽ vấn đề chỉ thuần tuý toán học thôi. Bạn đọc thử tự cài đặt xem sao.

c. Diện tích đa giác.

Để tính diện tích đa giác ta dùng cách tính diện tích của một hình bị giới hạn bởi các đường bất kỳ (kiến thức vi phân). Trong trường hợp này mọi đường giới hạn đều là đường thẳng nên việc tính toán cũng khá dễ dàng. Ta thử tham khảo thủ tục sau:

function Area: Real;

var

i: Integer;

S: Real;

begin

p[n + 1] := p[1];

S := 0;

for i := 1 to n + 1 do

S := S + (p[i].x – p[i – 1].x)*(p[i].y + p[i – 1].y);

Area := Abs(S)/2;

end;

Việc ta lấy trị tuyệt đối của S là có lý do của nó. Nếu đi theo thứ tự p[1], p[2],…, p[n] là ngược chiều kim đồng hồ thì ta sẽ có S âm, còn ngược lại ta sẽ nhận được S dương. Điều này cũng khá quan trọng trong một số trường hợp cụ thể.

Chú ý: một định nghĩa chính xác hơn cho khái niệm thuận hay ngược chiều kim đồng hồ là như sau: Nếu ta đang đi thuận chiều kim đồng hồ thì phần trong của đa giác luôn ở bên phía tay phải ta, còn phía bên tay trái là phần ngoài đa giác. Tất nhiên sẽ là ngược chiều kim đồng hồ trong trường hợp còn lại.

2. Điểm nằm trong đa giác.

Bài toán: Cho một đa giác không tự cắt, hãy kiểm tra xem một điểm có nằm trong đa giác hay không?

Tư tưởng cho bài toán này nói qua thì rất đơn giản và dễ hiểu: Từ điểm cần kiểm tra ta kẻ một tia bất kỳ, nếu tia đó giao với đa giác một số chẵn lần thì có nghĩa là nó nằm ngoài đa giác, một số lẻ lần thì nó nằm trong đa giác.

Nhưng trên thực tế có rất nhiều trường hợp cần phải được giải quết triệt để:


Một số trường hợp gây khó khăn cho thuật toán

Vì vậy, thuật giải của bài toán là như sau: Ta đi vòng quanh đa giác, mỗi khi ta đi từ một bên của tia sang một bên khác thì ta tính là một lần giao với đa giác. Dưới đây là một cách cài đặt, bạn đọc có thể cải tiến nó hoặc là tìm ra một cách cài đặt khác hay hơn. Ta dùng lại hàm Intersect đã nói ở phần trước.

Để tiện lợi, ta coi luôn đỉnh 1 là đỉnh thấp nhất của đa giác (có toạ độ y nhỏ nhất). Hơn nữa, việc ta chọn tia là tuỳ thích, vì vậy ta sẽ chọn tia song song và cùng chiều với chiều dương của trục Ox, như vậy sẽ rất dễ dàng cho tính toán.

function Inside(t: Point): Boolean;

var

Count, i, l: Integer;

Ray, li: Line;

begin

if t.y <= p[1].y then

begin {nếu t nằm dưới điểm thấp nhất của đa giác}

Inside := False;

Exit;

end;

Ray.p1 := t;

Ray.p2.y := t.y;

Ray.p2.x := max; {max là giá trị đủ lớn để lớn hơn mọi giá trị mà ta có thể xét đến}

p[0] := p[n];

p[n + 1] := p[1];

Count := 0;

l := 1; {biến l luu chỉ số điểm cuối cùng không nằm trên đường thẳng y = t.y}

i := 1;

while i <= n + 1 do

begin

if (p[i].y = t.y) and (t.x <= a[i].x) then

begin {nếu điểm i nằm trên tia}

while p[i].y = t.y do Inc(i);

{đi tiếp trên đa giác, tìm điểm đầu tiên không thuộc đường thẳng y = t.y. Ta yên tâm vòng lặp luôn dừng vì p[n + 1] = p[1]}

if (p[i].y - t.y)*(p[l].y - t.y) < 0 then Inc(Count);

end

else

begin

li.p1 := p[l];

li.p2 := p[i];

if Intersect(Ray, li) then Inc(Count);

end;

l := i;

Inc(i);

end;

Inside := Odd(Count);

end;

Trường hợp đặc biệt:

Đối với đa giác có toạ độ đỉnh nguyên, ta có thể không phải cài đặt phức tạp như trên. Nếu toạ độ điểm cần xét cũng nguyên, ta “xoay” tia cần xét đi một góc đủ nhỏ để loại đi trường hợp tia đi qua các đỉnh của đa giác. Còn nếu toạ độ điểm cần xét không nguyên thì hiển nhiên là không phải lo tia cần xét đi qua đỉnh của đa giác. Lúc này ta chỉ việc xét tất cả các cạnh của đa giác, cạnh nào cắt tia cần xét thì ta tăng biến đếm lên 1…

Nói chung, để xác định một điểm có nằm trong một đa giác hay không, ta mất một chi phí thuật toán là O(N). Nhưng đấy là trong trường hợp tổng quát, với một đa giác bất kỳ. Nhưng trong thực tế, nhiều khi ta gặp những trường hợp đặc biệt hơn nhiều. Trong những trường hợp đó ta không thể cứ áp dụng một cách thô thiển thuật toán trên vào được vì phải trả giá một chi phí thuật toán quá đắt.

Bài toán: Cho một đa giác lồi, hãy xác định xem một điểm có nằm trong đa giác đó hay không?

Ta hãy tận dụng tính “lồi” của đa giác. Vì là đa giác lồi nên nó chỉ giao với một đường thẳng bất kỳ tại không quá hai điểm (chính xác thì là 2 hoặc là 0). Chú ý, “giao” ở đây là khi ta đi vòng quanh đa giác, ta đi từ một bên của đường thẳng sang bên kia của nó.

Đến đây, hẳn nhiều bạn cũng đã rõ thuật toán. Thay bằng việc ta đi vòng quanh đa giác, ta chỉ tìm hai cạnh của đa giác cắt đường thẳng chứa điểm cần xét. Tất nhiên trường hợp không đoạn nào như vậy là tầm thường. Cũng có trường hợp có nhiều hơn hai đoạn như vậy nếu đường thẳng y = t.y đi qua đỉnh của đa giác. Nhưng cũng chẳng đáng chú ý, ta chọn một trong hai đoạn bất kỳ chứa đỉnh đó thôi. Sau khi chọn được hai cạnh của đa giác rồi, ta xét xem có bao nhiêu cạnh (trong hai cạnh) cắt tia cần xét. Để đơn giản, ta cũng trọn đường thẳng là đường y = t.y, và tia có hướng cùng chiều với chiều dương của trục Ox (Với cách trọn bất kỳ cũng không thực sự phức tạp hơn, bạn đọc hãy thử coi nó như là một trò giải trí?)







Chú ý rằng chi phí chủ yếu cho thuật toán này lại là phép tìm kiếm. Vì vậy, nếu ta áp dụng phép tìm kiếm tuần tự vào đây thì đúng là vô nghĩa. Bằng cách chia đa giác làm hai nửa, phân các nhau bởi hai điểm thấp “nhất” và “cao” nhất (hai đỉnh tô đậm trên hình vẽ). Ta chỉ phải tìm kiếm nhị phân (xin đọc phần “cấu trúc dữ liệu và giải thuật”) trên hai nửa này thôi, mỗi nửa sẽ tìm ra một cạnh thoả mãn. Ta tìm điểm i có toạ độ lớn nhất nhưng nhỏ hơn t.y, cạnh (p[i], p[i + 1]) sẽ là cạnh cần tìm. Như vậy, chi phí thuật toán cho bài toán này tỷ lệ với LogN. Đến đây, mọi việc gần như đã được giải quyết, các công việc còn lại là bài tập thực hành của bạn đọc.

Thuật toán chẳng có ý nghĩa gì khi câu hỏi “một điểm có nằm trong đa giác hay không?” chỉ được dùng có một lần. Nhưng trong trường hợp phải trả lời nhiều lần câu hỏi như vậy thì thuật toán thực sự đã phát huy tác dụng.

3. Bao lồi.

Bao lồi của một tập hợp điểm được định nghĩa là một đa giác lồi nhỏ nhất chứa toàn bộ tập điểm này. Một cách tương đương, bao lồi là một đường ngắn nhất bao quanh tập điểm. Bao lồi có một số tính chất dễ dàng nhận ra là: các đỉnh của nó phải thuộc tập điểm đã cho; với một đường thẳng bất kỳ nằm ngoài bao khi rời về phía bao thì sẽ chạm một trong các đỉnh của bao.

Bài toán: Cho tập điểm, tìm bao lồi của nó?

Chúng ta tạm bỏ qua một số ví dụ cực đoan như: tất cả tập điểm đếu nằm trên một đường thẳng?!!!...

a. Thuật toán bọc gói.

Đây là một giải thuật rất “con người”. Bắt đầu bằng việc chọn một điểm chắc chắn thuộc bao, dùng một tia quét ngược chiều kim đồng hồ cho đến khi gặp một điểm khác, ta được thêm một đỉnh thuộc bao, lại tiếp tục với điểm vừa tìm được…Quá trình kết thúc khi gặp lại đỉnh đầu tiên.



Các bước của thuật toán

Có nhiều cách chọn điểm đầu tiên, một trong cách đó là ta chọn điểm có hoành độ nhỏ nhất trong các điểm có tung độ nhỏ nhất.

Một điều đáng chú ý ở đây là việc quét một tia ngược theo chiều kim đồng hồ để tìm điểm đầu tiên chạm phải thực chất là ta tìm điểm mà tia nối từ điểm gốc tới nó tạo với trục hoành một góc bé nhất (điều này khá dễ hiểu thôi). Vì vậy chúng ta cũng cần phải biết cách tính góc khi cho điểm gốc và điểm cần xét đã. Nhưng chỉ với việc sắp xếp (tìm góc nhỏ nhất) thôi mà phải làm phức tạp đến vậy thì thật là uổng công. Ta có thể đưa ra một thứ tự hoàn toàn giống với việc tính góc cụ thể mà chương trình thì đơn giản hơn nhiều:

function Angle(p1, p: Point): Real;

var

dx, dy, ax, ay, t: Real;

begin {p là điểm gốc}

dx := p1.x – p.x;

dy := p1.y – p.y;

ax := Abs(dx);

ay := Abs(dy);

if ax + ay < Eps then t := 0

else t := dy/(ax + ay);

if dx < 0 then t := 2 – t

else

if dy < 0 then t := 4 + t;

Angle := t;

end;

Sau đây là thủ tục tìm bao lồi theo thuật toán bọc gói.

procedure Wrap;

var

i, li: Integer;

min, tmp: Real;

t: Point;

begin

t := p[1];

li := 1;

for i := 2 to n do

if (p[i].y < t.y)or(p[i].y = t.y)and(p[i].x < t.x) then

begin

t := p[i];

li := i;

end;

p[n + 1] := t; {để phát hiện thời điểm kết thúc}

m := 0; {m sẽ là số điểm trên bao}

repeat

Inc(m);

p[li] := p[m];

p[m] := t;

min := max;

for i := m + 1 to n + 1 do

begin

tmp := Angle(p[i], p[m]);

if (tmp < min) or ((tmp = min) and

(Abs(t.x–p[m].x) < Abs(p[i].x–p[m].x))) then

begin {nếu nhiều điểm thoả mãn, chọn điểm ở xa nhất}

min := tmp;

li := i;

t := p[i];

end;

end;

until li = n + 1;

end;

b. Thuật toán Graham.

Thuật toán bọc gói đòi hỏi một chi phí là O(M*N) (trong đó M là số điểm trên bao). Vì vậy nó chỉ làm việc tốt trong trường hợp số điểm nằm trên bao nhỏ hơn nhiều so với tổng số. Nhưng trong trường hợp xấu nhất (tất cả mọi điểm đều nằm trên bao) thì chi phí thuật toán sẽ lên tới O(N2) - rất tồi tệ! Chúng ta sẽ tiếp cận một phương pháp tốt hơn – phương pháp quét Graham. Phương pháp này có chi phí thuật toán ổn định và không tốn kém lắm. Hầu như tất cả chi phí là dành cho việc khởi một tạo đường khép kín đơn từ tập điểm đã cho.

Chọn điểm chốt có hoành độ x lớn nhất trong các điểm có tung độ y nhỏ nhất (khi hiểu rõ thuật toán các bạn sẽ biết được nguyên nhân). Chuyển điểm chốt về vị trí 1 để tiện cho tính toán. Ta sắp xếp các điểm theo khoá là góc tạo bởi điểm đó và điểm chốt với trục hoành theo thứ tự tăng dần. Khi đi theo thứ tự p[1], p[2], …p[N], p[1] ta thu được một đa giác khép kín đơn.

Ta đi vòng qua đa giác này, thử đặt một điểm vào bao và kiểm tra xem các điểm trước đó có còn nằm trên bao hay không. Nếu không ta chỉ việc loại điểm đó ra khỏi bao thôi.

Việc kiểm ra một điểm có còn nằm trên bao hay không có thể làm như sau: khi cho một điểm mới vào bao, ta sẽ lần ngược lại những điểm đã nằm trong bao. Trong quá trình, nếu gặp một điểm là khúc rẽ phải thì điểm này sẽ không thuộc bao nữa, ta loại nó luôn. Quá trình kết thúc khi ta gặp một điểm là khúc rẽ trái, vì tất cả các điểm từ đó lùi về 1 chắc chắn sẽ thuộc bao.

Các bước của thuật toán.

Cài đặt không phải là một vấn đề khó nhưng phải cảnh giác với sai số và các điểm thẳng hàng.

Việc xây dựng đường khép kín đơn không thực sự phải dùng hàm Angle vì dễ gây sai số và chi phí hơi lớn. Vì tất cả các tia tạo bởi điểm chốt và một điểm bất kỳ đều trong góc phần tư I và II nên ta có thể dùng hàm Lower sau để làm phép so sánh cho việc sắp xếp.

function Lower(p1, p2: Point): Boolean;

var

a1, b1, a2, b2: Real;

begin

a1 := p1.x – p[1].x;

b1 := p1.y – p[1].y;

a2 := p2.x – p[1].x;

b2 := p2.y – p[1].y;

Lower := a1*b2 > a2*b1;

end;

Thực chất ta đã so sánh hai giá trị a1/b1 và a2/b2, tức là cotg của hai góc. Nhưng ta không làm như vậy vì phải xét b1, b2 liệu có bằng 0 hay không.

Sau đây là đoạn chương trình miêu tả phương pháp quét Graham. Ta coi mọi công việc khởi tạo đã xong xuôi. Hàm CCW đã nói tới ở phần trước.

procedure GrahamScan;

var

i: Integer;

begin

m := 2;

for i := 3 to n do

begin

while CCW(p[m - 1], p[m], p[i]) <> 1 do Dec(m);

Inc(m);

p[m] := p[i];

end;

end;

Chi phí cho thủ tục trên tỷ lệ thuận với N. Đúng vậy, mặc dù trong vòng lặp có một vòng lặp, nhưng ta để ý là không điểm nào bị loại quá một lần nên vòng lặp này chỉ hoạt động không đến N lần.

Như vậy chi phí cho thuật toán này là O(NlogN) nếu ta dùng phương pháp sắp xếp tốt (như Quick Sort chẳng hạn).

c. Cải tiến.

Ta có thể làm giảm chi phí tính toán đi rất nhiều bằng cách loại bỏ những điểm chắc chắn không thuộc bao.

Ví dụ như ta loại đi những điểm nằm hoàn toàn trong tứ giác có các đỉnh là các điểm có hoành độ lớn nhất, hoành độ nhỏ nhất, tung độ lớn nhất, tung độ nhỏ nhất. Đối với những bộ dữ liệu được tạo một cách ngẫu nhiên thì việc này rất có ích. Nhưng nếu tất cả các điểm đều thuộc bao thì việc này là vô nghĩa. Nói chung mọi cách tham lam thì cũng đều tốt trong một số trường hợp nhất định mà thôi.

4. Cặp điểm gần nhất.

Bài toán: Cho tập điểm, hãy tìm cặp điểm có khoảng cách nhỏ nhất trong tập điểm trên.

Một cách thô thiển ta có thể xét tất cả các cặp điểm và lưu lại cặp điểm có khoảng cách nhỏ nhất. Nhưng như vậy thì chi phí thuật toán sẽ là O(N2). Ta hoàn toàn có thể giải quết bài toán này với chi phí là O(NlogN) với việc áp dụng tư tưởng “chia để trị” của thuật toán Merge Sort (xin đọc phần “cấu trúc dữ liệu và giải thuật”). Ý tưởng thuật toán như sau: ta sắp xếp các điểm theo hoành độ (hoặc tung độ cũng được). Tại mỗi bước ta chia tập làm hai phần thì cặp điểm gần nhất sẽ nằm ở một trong hai phần hoặc là cặp điểm mà mỗi điểm thuộc một phần.
Vấn đề là phải xử lý trường hợp mỗi điểm nằm ở một phần, còn trường hợp cả hai điểm đều thuộc một phần thì đã được giải quyết vì lời gọi đệ qui. Ta có thể sử dụng ngay thứ tự sắp xếp và khoảng cách min đã tìm được được để làm cận cho trường hợp xét trên hai phần. Khi xét mỗi điểm ở nửa này, nếu gặp điểm ở nửa kia có hiệu hoành độ đến nó không nhỏ hơn khoảng cách min đã tìm được thì ta dừng luôn vì tập điểm đã được sắp theo x.

Nhưng như vậy vẫn có thể gặp phải trường hợp xấu: các điểm nằm sát hai bên đường phân cách; trong trường hợp đó, nếu xử lý không tốt thì chi phí có thể sẽ là O(N2)
trường hợp xấu Ta giải quyết vấn đề này bằng cách sắp các điểm theo tung độ y và xét tương tự như trên. Chú ý, nếu tại mỗi bước ta lại gọi thủ tục sắp xếp mỗi nửa thì chi phí thuật toán sẽ là O(Nlog2N), không phải là thực sự tốt lắm. Nhưng để ý một chút, ta thấy mỗi nửa đều được sắp xếp, hơn nữa cách làm của ta cũng đang dựa vào tư tưởng của Merge Sort, như vậy tại sao ta không sắp xếp theo kiểu Merge Sort ngay trong thủ tục đệ quy của mình. Như vậy hai công việc đều được sử lý đồng thời. Chi phí cho bài toán này giống như chi phí sắp xếp bằng Merge Sort, tỷ lệ với NlogN.

Cài đặt thuật toán này không khó nhưng khá tỉ mỉ. Ta bỏ qua bước sắp xếp tập điểm theo hoành độ x. Đầu tiên là thủ tục trộn hai phần, tiếp theo là thủ tục đệ quy tìm cặp điểm gần nhất.

procedure Merge(l, r: Integer);

var

t: Polygon;

i, j, m, c: Integer;

begin

m := (l + r) div 2;

i := l;

j := m + 1;

for c := 1 to r – l + 1 do

if (j > r) or (p[i].y < p[j].y) then

begin

t[c] := p[i];

Inc(i);

end

else

begin

t[c] := p[j];

Inc(j);

end;

for c := 1 to r – l + 1 do p[l + c - 1] := t[c];

end;

procedure MinDist(l, r: Integer);

var

i, j, j1, m: Integer;

begin

if l = r then Exit;

m := (l + r) div 2;

MinDist(l, m);

MinDist(m + 1, r); {gọi đệ quy tìm min trên hai phần}

j1 := m + 1;

for i := l to m do

begin

while (j1 <= r)and(p[j1].y – p[i].y >= min) do Inc(j1);

for j := j1 to m do

if p[j].y – p[i].y >= min then Break

else

if Dist(p[i], p[j]) < min then

begin {cập nhật kết quả}

min := Dist(p[i], p[j]);

Result.x := p[i];

Result.y := p[j];

end;

end;

Merge(l, r); {trộn hai phần}

end;

Result là biến lưu kết quả, có cấu trúc giống như kiểu Line. Biến min dùng để lưu khoảng cách nhỏ nhất tìm được cho đến thời điểm hiện tại.

Cái ni chú đem lên VNOI thì hay hơn :?: :?: :?: . Đổi chủ đề đi. Nói về mấy cấy tin học thực tế chút đi :bounce:

ê có thuật toán chi tìm trong số n điểm có bao nhiêu điểm cùng thuộc 1 đường thằng thì hay hơn nhiều
ko thì mấy cái ni có trong lý thuyết

Kấy ni cho mấy chú thôi

ặc, răng mà chộ mô thằng Đô Lâng cụng bu vô được hềy???
đề nghị anh em ban nic hắn lại đi :twisted: :twisted: :twisted:

frozenwinter đã viết:

ặc, răng mà chộ mô thằng Đô Lâng cụng bu vô được hềy???
đề nghị anh em ban nic hắn lại đi :twisted: :twisted: :twisted:

Tau thì thấy chỗ nào có tau là có mi chạy theo sau
Ko bít làm gì nữa

hì hì, tau chỉ chạy theo để ngăn chặn tội ác thui

Đít tra ơi cho cứt sót chạy với mồ! :lol:

uh, Cứt Sót với Đít Tra cùng chạy tập thể dục đi :bounce: :bounce: :bounce:
cho khoẻ người hềy

những chỗ chơi bời thế này thằng tú anh đem mấy cái đó làm chi biết
nhìn đau mắt
chả ai thèm đọc

arshavin đã viết:

những chỗ chơi bời thế này thằng tú anh đem mấy cái đó làm chi biết
nhìn đau mắt
chả ai thèm đọc

ai nói, tau đọc nầy! :P :P :P :P :P :P

mà thằng Tuấn Minh lạnh lùng hềy?
không đọc thì có tau đọc :evil:

frozenwinter đã viết:

mà thằng Tuấn Minh lạnh lùng hềy?
không đọc thì có tau đọc :evil:

Tuấn Minh lạnh lùng, zoooooo :bounce: :bounce: :bounce: :bounce: :bounce: :bounce: :bounce: :bounce: :bounce: :bounce: :bounce:

bay bị chi à?
tự dưng nói t lạnh lùng.
oan quá
:pale:
hồng trúc đọc hết?không tin
:lol:

arshavin đã viết:

bay bị chi à?
tự dưng nói t lạnh lùng.
oan quá
:pale:
hồng trúc đọc hết?không tin
:lol:

Minh mà lạnh lùng á, bây có nói nhầm hàng không, Minh cha của ... cute :twisted: :twisted: :twisted:

có mà Khu toe

frozenwinter đã viết:

có mà Khu toe

Không được nói TMinh rứa, xử tử đó :twisted: :twisted: :twisted:

hì hì, ta đùa mà :P :P :P

:lol: :lol: :lol:
may còn quỳnh vẫn chưa nói t lạnh lùng
điên mà lạnh lùng 8) :lol:
:lol: :lol:

bêy mần raeng mà ko hỉu chi cả

Đề ngị anh em sang cho khác tán phét nhau! đây là nơi học tập cơ mà!