• Thuật giải quá khó, không nghĩ ra.
• Nghĩ ra được thuật giải, nhưng không cài đặt được vì quá phức tạp.
• Thuật giải tốt, cài đặt xong, nhưng vẫn không ổn do những lỗi nho nhỏ tinh vi và khó tránh.

Trong bài viết này, tôi xin được trình bày về một phương pháp có thể áp dụng cho một lớp rất lớn các bài toán tin có nội dung hình học: đó là phân rã bài toán ban đầu ra, đưa nó về một vài mô hình thật là đơn giản và cài đặt chỉ cần trình độ trung bình khá là ổn. Nội dung chính của phương pháp này mà tôi muốn nói cùng các bạn là:

• Coi một góc là tập hợp vi phân các góc nhỏ liên tiếp. (1)
• Coi một bao hình là một tập hợp vi phân các điểm liên tiếp. (2)

Tất nhiên từ “vi phân” ở đây chỉ mang tính hình tượng, tức là một số vừa đủ lớn các góc vi phân, hay các điểm vi phân để cho (1) và (2) có thể coi như là đúng.

Chúng ta sẽ đưa vấn đề đi cụ thể hơn sau khi phân tích một số bài tin sau đây:

1. Diện tích trong tam giác (Problem G - The 2004 ACM Asia Programming Contest - Beijing):
Cho một tam giác và một vòng dây kín có độ dài biết trước. Hãy dùng vòng dây đó để khoanh một vùng kín nằm gọn trong tam giác sao cho diện tích phần thu được là lớn nhất.

Input: Gồm nhiều bộ test, mỗi bộ gồm đúng bốn số dương được viết trên cùng một dọ̀ng. Ba số đầu tiên là độ dài ba cạnh của tam giác, số cuối cùng là chu vi vòng dây. Độ dài các cạnh của mảnh vườn không quá 100. Độ dài vòng dây không lớn hơn chu vi tam giác.

Output: Gồm nhiều dọ̀ng, mỗi dọ̀ng ứng với một dọ̀ng trong input, chỉ ghi một số là diện tích lớn nhất có thể được, làm trọ̀n với đúng hai chữ số sau dấu thập phân.

Ví dụ:
Input:
12.0000 23.0000 17.0000 40.0000
84.0000 35.0000 91.0000 210.0000
100.0000 100.0000 100.0000 181.3800
Output:
89.35
1470.00
2618.00

Có thể không khó khăn lắm để nhận ra được thuật giải của bài toán này như sau: Tìm O là giao ba đuờng phân giác của tam giác đó. Ta gọi R là bán kính đường tròn tâm O (bạn cứ coi là có R rồi). Phần diện tích tối ưu là phần mà vừa nằm trong đường tròn vừa nằm trong tam giác, đồng thời chu vi của phần diện tích đó đúng bằng L là chu vi vòng dây. Còn để tìm R thì ta chặt nhị phân.

Chúng ta sẽ không bàn nhiều về thuật giải bài toán, cứ coi là bạn biết rồi đi. Vậy vấn đề là bạn sẽ cài đặt nó như thế nào? Quả thật rất khó để có thể hoàn thành bài này trong thời gian cho phép nếu như ta cứ cài đặt một cách thuần túy thông thường. Như vậy thì chẳng những mất thời gian mà hiệu quả đạt được còn là rất thấp.

Sở dĩ bài này khó cài đặt là bởi vì ứng với mỗi R ta có rất nhiều trường hợp có thể xảy ra về vị trí tương đối của hình tròn (O) và tam giác ABC. Số điểm giao nhau có thể không có, có thể có một, có hai, ..., hoặc có sáu giao điểm. Các giao điểm lại không xếp theo quy luật gì nên lúc thực sự tính toán lại nảy sinh nhiều vấn đề rất phức tạp, ví dụ như trên mỗi cạnh có mấy giao điểm? Điều này phải xác định rõ ràng, nếu không thì không thể tính được chu vi và diện tích của hình cần thiết. Tính sơ sơ ra số trường hợp cần xét cũng quá lớn và trong mỗi trường hợp cũng đủ rắc rối để cho ta có thể giải quyết bài này một cách nhanh gọn và chính xác (Tôi đã làm thử rồi). Vậy nếu đây là một bài thi quan trọng thì trong phòng thi liệu bạn có đủ bình tĩnh để làm một cách chính quy như trên? Tôi xin phát biểu phương án về cách phân rã bài toán này, để biến nó thành một bài toán đơn giản và rất dễ cài đặt, và từ đó tổng quát hóa lên một phương án tuyệt vời:

Đầu tiên phải thấy được là cái khó chỉ là làm sao xác định rõ những giao điểm cần thiết. Gọi (T) là hình tạo bởi (0) và ABC ứng với R biết trước. Rõ ràng là (T) là một hình gồm có những phần đoạn thẳng (thuộc tam giác ABC) và những phần đường tròn (thuộc (O)). Bây giờ ta không quan niệm (T) như vậy nữa, ta coi nó gần đúng là một đa giác (T) gồm rất nhiều điểm Mi, với 1  i  P, với P bạn khai báo const ở đầu chương trình, P càng lớn càng tốt, nhưng không nên quá lớn vì chương trình sẽ chạy lâu hơn.

Xác định các điểm Mi: Ta chia góc 360 tại O ra làm P góc đều nhau. Ứng với góc thứ i đó ta vẽ một tia Oi, sau đó ta xác định xem tia Oi cắt hình tròn trước hay cắt tam giác trước. Mi chính là giao điểm gần O nhất trong hai giao điểm đó.

Như vậy là thay vì phải tính toán với miền (T) vô cùng rắc rối, nếu ta coi nó như là một đa giác (T) gồm P đỉnh và xác định các điểm Mi dễ dàng như trên, thì công việc còn lại thật vô cùng đơn giản. Nhưng còn vấn đề sai số? Ta có thể khắc phục nó bằng một thủ thuật như sau:

Đặt M0 = MP và MP+1 = M1. Xác định 6 điểm i mà góc giữa Mi-1, Mi, Mi+1 là lớn nhất. Đó chính là sáu giao điểm gần như thực sự của (T). Bây giờ ta tính toán trực tiếp trên (T) bằng cách dùng các công thức chính xác cho cung tròn và đoạn thẳng thì vấn đề sai số coi như không còn.

Bạn thấy đó, cùng là một bài toán, nhưng nếu ta quan niệm nó khác đi một chút thì công việc sẽ được giảm tải đi rất nhiều lần. Không phải cứ cái gì tốt nhất về mặt lý thuyết cũng là tốt nhất với ta, nhất là trong các kỳ thi. Điều quan trọng là tính hiệu quả và thực tế của chương trình. Việc phân rã một hình (T) ra thành đa giác (T) cũng là điều thường gặp ở nhiều nơi, nhưng thủ thuật tách ra để rồi ghép lại thì quả là rất độc đáo. Thủ thuật này trong toán thường gặp khi phải tính tổng của một chuỗi số S, hay một chuỗi hàm f. Khi đó người ta hay vi phân vế trái, tính toán một hồi cho nó thật gọn rồi lại tích phân chính vế trái đó. Nếu như bạn để ý, về bản chất thì đó cũng là điều mà bài tin kia đã sử dụng, cho dù nó đã bị “tin hóa” đi bởi tham số P. Nhưng bạn cứ yên tâm, không có gì là tuyệt đối cả, nếu như P đủ lớn (khoảng vài nghìn) thì kết quả sẽ luôn ra tối ưu. Bài tin trên đã áp dụng cả (1) và (2) để giải quyết hiệu quả vấn đề. Có lẽ bạn vẫn chưa hình dung ra phương pháp này ra sao? Chúng ra hãy cùng bàn tiếp trong bài tiếp theo:

2. Chocolate

Nhà máy sản xuất bánh kẹo Fishburg sản xuất ra một loại bánh chocolate hình đa giác lồi. Kiddy và Carlson mua một cái và họ muốn cắt nó ra làm hai phần bằng nhau với một nhát cắt có độ dài nhỏ nhất. Viết chương trình tìm độ dài nhỏ nhất để cắt miếng bánh sử dụng những gì bạn được cho biết về miếng bánh. Tổng số đỉnh N là một số nguyên (3  N  50). Tọa độ của các đỉnh là tập hợp các cặp số thực -100  x_i , y_i<= 100.

Input: Dòng đầu của input file gồm số N - số lượng đỉnh của đa giác. N dòng sau gồm toạ độ của các đỉnh liên tiếp nhau của đa giác.

Output: gồm độ dài nhỏ nhất của đường cắt chính xác đến 0,0001.

Ví dụ:

Input:
4
0 0
0 3
4 3
4 0
Output:
3

Thuật giải tốt của bài này theo tôi là không phù hợp để bàn ra ở đây vì cái lõi toán của nó nhiều quá. Nói chung để mà vừa nghĩ thuật giải tốt hẳn và cài đặt xong nó chắc cũng phải vất vả nhiều lắm mà cũng chẳng biết là liệu mình có kiểm soát được không nữa. Vậy chúng ta cùng bàn cách phân rã bài này ra cho nó đơn giản đi nhé.

Cách đơn giản nhất ai cũng có thể nghĩ ra là coi như đa giác này là một tập hợp các điểm rời rạc, sau đó ta lấy hai trong số những điểm đó, rồi kiểm tra xem đoạn thẳng nối hai điểm này có chia đôi được đa giác hay không, nếu như được rồi thì cập nhật kết quả thôi. Cải tiến của cách này là chỉ chọn một điểm thôi, điểm còn lại thì chặt nhị phân. Cách này về tư tưởng phân rã thì là tốt nhưng trên thực tế không phải là không có vấn đề. Điều kiện các tọa độ của đa giác có trị tuyệt đối không quá 100 cho nên sẽ vẫn có những test mà chu vi của nó sẽ khá là lớn (có thể lên tới hàng vạn). Mà theo như cách phân rã này thì độ sai số sẽ tỉ lệ theo chu vi của đa giác. Nếu chia đa giác thành P điểm, với độ phức tạp của cách này vượt quá Plog(P), thì rõ ràng muốn chạy nhanh được thì P không thể tới hàng vạn, cho nên khả năng chính xác tới nhiều chữ số sau dấu thập phân khi chu vi của đa giác quá lớn là điều không tưởng. Vậy (2) không dùng được ở đây.

Cách thứ hai có thể khắc phục nhược điểm trên, là ta phân rã các góc ra thành vô số các góc nhỏ vi phân. Giả sử số góc là P, thì một góc sẽ có giá trị là dP = 360/P. Chắc hẳn đọc đề bài lần đầu ai cũng tưởng tượng là đa giác thì đứng yên, còn đường thẳng chia đôi đa giác sẽ xiên xiên. Ta hãy tưởng tượng ngược lại một chút như sau: Đường thẳng chia đôi đa giác thì luôn nằm ngang, có thể tịnh tiến lên xuống, còn đa giác thì có thể xoay. Về bản chất thì vẫn không có gì thay đổi, nhưng nó sẽ giúp ích nhiều cho ta. Tóm lại thuật giải sẽ như sau:

• Xoay đa giác đi một góc dP.
• Chặt nhị phân để tịnh tiến đường thẳng nằm ngang sao cho nó chia đôi đa giác kia. Nếu không chia vừa thì bằng cách chặt nhị phân ta có thể tịnh tiến đường thẳng này lên xuống đến bao giờ bằng nhau thì thôi.
• Sau khi đã chia đôi đa giác, cập nhật lại độ dài tốt nhất của nhát cắt.

Sau khi xoay đi P lần, mỗi lần một góc dP thì đa giác sẽ quay về đúng vị trí ban đầu. Nếu như có bạn nào chưa biết công thức xoay hình, tôi xin được viết luôn ra đây:


xmới = x_cũx cos(alpha) – y_cũx sin(alpha).
ymới = x_cũx sin(alpha) + y_cũx cos(alpha).

Trong đó alpha là góc quay.

Tất nhiên P càng lớn thì càng tốt. Đối với bài này tôi để P = 35000/N và chạy đúng hết tất cả các test. Đó chính là kết quả của việc áp dụng tính phân rã thứ (1).

Kết luận: Có rất nhiều phương pháp để giải quyết một bài toán tin, chọn cách làm nào là tùy bạn. Một lời khuyên không bao giờ cũ của những người đi trước đối với tất cả chúng ta là: Không hẳn trong mọi sự lựa chọn ta đều lấy cái tốt nhất, hãy chọn cái phù hợp nhất đối với bạn. Trong phòng thi tâm lý ổn định là một điều rất quan trọng để dẫn tới thành công. Nhưng tâm lý sao ổn được khi bạn đang làm một việc quá sức mình? Nghệ thuật phân rã bài toán không phải là cái tốt nhất trong mọi trường, đó là điều chắc chắn. Nhưng nếu như trong một vài trường hợp cụ thể nào đó, có thể nó sẽ phù hợp với bạn đấy!
Và sau cùng là một bài tập luyện tập dành cho bạn.

Bricks - 2002-2003 ACM Northeastern European Regional Programming Contest(Đề bài được tôi tóm tắt) Có viên gạch kích thước A × B × C inches. Trên sàn nhà có một cái lỗ kích thước D × E inches, coi như cái lỗ là rất sâu. Hỏi liệu có thể xoay sở làm sao để nhét được viên gạch vào trong lỗ trên hay không? Input: Gồm 5 số A, B, C, D, E, mỗi số không nhỏ hơn 1, không lớn hơn 10 và có nhiều nhất một chữ số sau dấu thập phân. Output: Ghi “YES” nếu như có thể nhét gạch vào lỗ, ngược lại ghi “NO”.

Ví dụ:
Input: 2.0 1.5 1.4 1.0
Output: NO
Input: 2.0 1.5 1.5 1.0
Output: YES

School@net (Theo Tạp chí TH&NT)