05.2 - Thảo luận bài tập

Giới thiệu

Hình học là một mảng rất rộng trong toán học và có tầm ảnh hưởng trải rộng trên nhiều lĩnh vực của Tin học ngày nay. Do đó các bài toán về hình học xuất hiện trong lập trình nói chung và lập trình thi đấu nói riêng rất đa dạng. Trong chuyên đề này chúng ta sẽ thảo luận qua một số dạng hay gặp. Các phần nâng cao hơn sẽ được giới thiệu ở các chuyên đề sau.

Một số dạng thường gặp:

1. Vị trí tương đối của điểm so với đường thẳng, tia và đoạn thẳng

2. Giao của các đường thẳng, đoạn thẳng và tia

3. Khoảng cách: Cặp điểm gần nhất, khoảng cách từ điểm đến đường thằng, đoạn thẳng

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

5. Đa giác bao nhau, bao lồi của tập điểm

6. Các dạng tổng hợp nhiều kiến thức

Tài liệu tham khảo

• Tài liệu giáo khoa chuyên tin quyển 3, chuyên đề 8,  Hồ Sỹ Đàm

• Competitive Programming 4, book 2, chapter 7,  Steven Halim

• VNOI wiki, hình học

• USACO, Geometry

• Các tài liệu chuyên đề hình học của hội thảo các trường chuyên Duyên hải Bắc Bộ 2018, 2021

1. Vị trí tương đối của điểm so với đường thẳng, tia và đoạn thẳng

Bài toán mở đầu: Điểm và đường thẳng

Cho điểm M(x0,y0), A(xA,yA), B(xB,yB). Yêu cầu:

a) Kiểm tra M có thuộc đường thẳng đi qua 2 điểm A, B hay không?

b) Kiểm tra M có thuộc đoạn thẳng AB hay không

c) Kiểm tra M có thuộc tia AB hay không

Nhắc lại phương pháp kiểm tra:

Đặt F(X,Y) = (yA-yB)X + (xB-xA)Y + (xAyB - xByA) (phương trình đường thẳng qua hai điểm A, B)

- Điểm M thuộc đường thẳng AB khi F(x0,y0) = 0

- Điểm M thuộc đoạn thẳng AB khi: F(x0,y0)=0 và Min(xA,xB) ≤ x0 ≤Max(xA,xB) và Min(yA,yB) ≤ y0 ≤ Max(yA,yB)

- Điểm M thuộc tia AB khi F(x0,y0) = 0 và có nghĩa là M phải thoả mãn điềukiện: F(x0,y0) = 0 và (x0-xA)(xB-xA)≥0 và (y0-yA)(yB-yA) ≥0

Bài toán 2: Điểm và đa giác

Cho đa giác không tự cắt A1A2...AN với các đỉnh Ai(xi,yi) nguyên. Với điểm A(xA,yA) cho trước, hãy xác định xem A có nằm trong đa giác đã cho hay không (Trong trường hợp trên cạnh đa giác xem như nằm trong đa giác)

Phương pháp: Thực hiện theo thuật toán ray casting đã đề cập trong tài liệu phần lý thuyết nền

Nhiệm vụ 1.1 - Point Location Test - CSES

Tóm tắt: Cho 3 điểm P1, P2, P3. Kiểm tra xem P3 nằm bên trái, phải hay "chạm" vào đường thẳng qua P1 và P2. Lưu ý rắng hướng nhìn của chúng ta là từ P1 đến P2.

Nhiệm vụ 1.2. Vị trí tương đối - Upcoder

Tóm tắt: Cho bốn điểm A, B, C, D. Tìm vị trí tương đối của hai điểm A, B so với đường thẳng C, D. Nếu A,B cùng phía xuất ra "Cung Phia", ngược lại xuất "Khac Phia"

Nhiệm vụ 1.3. Tập hợp điểm - Set of Points - Codeforce

Tóm tắt: Độ lồi của một tập hợp các điểm trên mặt phẳng là kích thước của tập hợp con lớn nhất của các điểm tạo thành một đa giác lồi. Nhiệm vụ của bạn là xây dựng một tập hợp n điểm với độ lồi chính xác là m. Tập hợp các điểm của bạn không được chứa ba điểm nằm trên một đường thẳng.

Input: Dòng đơn chứa hai số nguyên n và m ( 3 ≤ m ≤100, m ≤ n ≤2m ).

Output: Nếu không có giải pháp, hãy in " -1 ". Mặt khác, in n cặp số nguyên - tọa độ các điểm của bất kỳ tập hợp nào có độ lồi của m. Các tọa độ không vượt quá |10^8|.

Giao điểm của đường thẳng, đoạn thẳng và tia

Giao điểm hai đoạn thẳng

Bài toán: Cho 2 đoạn thẳng AB và CD với A(x1,y1), B(x2,y2), C(x3,y3), D(x4,y4). Tìm giao điểm (nếu có) của 2 đoạn thẳng

- Phương pháp:

B1. Tìm giao điểm M của 2 đường thẳng AB và CD

B2. Kiểm tra M có thuộc đồng thời cả 2 đoạn AB và CD hay không. Nếu có đó là giao điểm cần tìm, ngược lại kết luận không có.

Giao điểm của 2 đường thẳng

Bài toán: Cho 2 đường thẳng có phương trình a1x+b1y+c1=0 và a2x+b2y+c2=0. Tìm giao điểm (nếu có) của 2 đường thẳng trên.

- Phương pháp:

B1. Tính D = a1b2 - a2b1, Dx = c2b1 - c1b2, Dy = a2c1 - a1c2

B2. Xét 3 khả năng:

+ Nếu D=Dx=Dy=0 thì kết luận 2 đường thẳng trùng nhau

+ Nếu D=0 và ((Dx ≠  0) hoặc (Dy ≠ 0)) thì kết luận 2 đường thẳng song song

+ Nếu D≠ 0 thì kết luận 2 đường thẳng cắt nhau tại điểm có (Dx/D, Dy/D)

Giao điểm của tia và đoạn thẳng

Bài toán: Cho tia AM chứa điểm B (khác A) và đoạn thẳng CD với A(x1,y1), B(x2,y2), C(x3,y3), D(x4,y4). Tìm giao điểm (nếu có) của tia AM với đoạn thẳng CD.

- Phương pháp:

B1. Tìm giao điểm N của 2 đường thẳng AB và CD

B2. Kiểm tra N có thuộc tia AM và đoạn thẳng CD hay không. Nếu có đó là giao điểm cần tìm, ngược lại kết luận không có.

Nhiệm vụ 2.1. Tìm giao điểm - UPCODER

Tóm tắt: Cho 4 điểm A, B, C, D. Tìm giao điểm nếu có của hai đường thẳng AB và CD

Nhiệm vụ 2.2. Line Segment Intersect - CSES

Tóm tắt: cho 4 điểm A, B, C, D. Kiểm tra xem hai đường thẳng AB và CD có cắt nhau không, nếu có in ra "YES", ngược lại in ra "NO"

Nhiệm vụ 2.3. Point in Polygon - CSES

Tóm tắt: Cho một đa giác với n đỉnh, cho m điểm, nhiệm vụ của bạn là kiểm tra mỗi điểm này nằm trên, trong hay bên ngoài đa giác.

Gợi ý: sự dụng Ray Casting

Nhiệm vụ 2.4. Cắt hình - Duyên hải Bắc Bộ 2021

Tóm tắt: Một mảnh giấy hình chữ nhật được cắt bởi những nhát kéo. Cho biết toạ độ của mảnh giấy cũng như các nhát cắt, hãy xác định số mảnh được cắt rời. Giả thiết mảnh giấy được đặt trong một hệ toạ độ sao cho các mép giấy song song với các trục toạ độ, góc dưới trái của nó trùng với điểm (0; 0) và góc trên phải của nó trùng với điểm (m; n). Mỗi nhát cắt được xác định bởi hai đầu mút trên biên của mảnh giấy sao cho đảm bảo đoạn thẳng nối hai đầu mút này thực sự cắt mảnh giấy. 

Nhiệm vụ 2.5. Bộ ba điểm thằng hàng - Duyên hải Bắc Bộ 2021

Tóm tắt: Cho tập N điểm, đếm số bộ ba điểm thẳng hàng trong tập

Khoảng cách: Điểm đến đoạn thẳng, đường thằng, điểm đến điểm

Phần này chủ yếu áp dụng công thức theo lý thuyết, tuy nhiên có một số bài phải áp dụng một số kỹ thuật mở rộng hơn.

Nhiệm vụ 3.1. Khoảng cách điểm đến điểm, đoạn thẳng, đường thẳng tia

Codeforce - GYM - 100168

Thực hiện các bài: F, L, H, I, L

Đề bài: CodefoceGym_100168

Nhiệm vụ 3.2. Cặp điểm gần nhất - UVa 10245

Nhiệm vụ 3.3. UVa 00587 - There's treasure

Nhiệm vụ 3.4. UVa-10927 - Bright Lights

Nhiệm vụ 3.5. UVa-10263 - Railway

Diện tích đa giác

Diện tích các đa giác lồi thông dụng như tam giác, hình chữ nhật, hình thang,...được tính dựa theo các kiến thức hình học cơ bản đã biết. Cách tính diện tích một đa giác bất kỳ được diễn giải theo công thức Shoelace (Shoelace Fomular) dựa trên việc phân rã đa giác thành các hình thang có hai đáy song song trục tung, độ dài hai đáy này chính là tung độ của hai đỉnh liền kề của đa giác.

Nói một cách khác, cho một đa giác P với các n đỉnh lần lượt là p1, p2, ..., pn. Ta kẻ đường vuông góc từ tất cả các đỉnh của P xuống trục hoành, mỗi cặp đỉnh kề nhau tạo thành một hình thang vuông. Diện tích đa giác P được được tính dựa trên tổng các các hình thang này. Diện tích mỗi hình thang tính bằng công thức tích có hướng.

Các em có thể xem chi tiết cách diễn giải công thức tại Wikipedia - Shoelace fomular

Nhiệm vụ 4.1. Polygon Area - CSES

Nhiệm vụ 4.2. Loại đa giác  - Duyên hải Bắc Bộ 2021

Nhiệm vụ 4.3. Diện tích đa giác tự cắt - Duyên Hải Bắc Bộ 2021

Nhiệm vụ 4.4. Đổi đất - Đề chọn HSG QG 2004 - 2005

Nhiệm vụ 4.5. UVa-11447-Reservoir Logs

Dãy đa giác bao nhau, bao lồi của tập điểm

Phần này có thể kết hợp nhiều kiến thức toán học khác nhau, tuy nhiên, kiến thức nền tảng nhất vẫn dựa trên bao lồi của tập điểm.

Bao lồi của tập điểm

Cho tập hợp n điểm trên mặt phẳng. Bao lồi của tập này được định nghĩa là đa giác lồi có diện tích nhỏ nhất với các đỉnh thuộc tập đã cho và chứa tất cả n điểm ở bên trong hoặc biên của nó.

Các thuật toán để tìm bao lồi của tập điểm

Cho đến nay, chúng ta có nhiều thuật toán để tìm bao lồi của tập điểm, phố biến nhất là ba thuật toán: Gói quà (Gift Wrapping), Graham scan, và chuỗi đơn điệu (Monotone chain). Chi tiết về ý tưởng và triển khai cài đặt các em xem trong tài liệu của phần lý thuyết nền hoặc bài viết chi tiết trong VNOI. Trong phần này chúng ta sẽ thảo luận qua các bài tập liên quan của nó.

Nhiệm vụ 5.1. Bao lồi tập điểm - Convex Hull - Kattis

Nhiệm vụ 5.2. Pha chế  - Kmix - VNOJ

Nhiệm vụ 5.3. Câu chuyện người lính - Military - VNOJ

Nhiệm vụ 5.4. Thửa đất lớn nhất - Triland

Dãy đa giác bao nhau

Thông thường các bài toán về dãy đa giác bao nhau dựa vào diện tích, chu vi và kết hợp thuật toán quy hoạch động để giải.

Nhiệm vụ 5.5. Dãy tam giác bao nhau

Nhiệm vụ 5.6. Ruộng bậc thang

Nhiệm vụ 5.7. Test Hình học + sweepline 1

Để tham gia contest, các em truy cập vào Oganization

Nhiệm vụ 5.8. Test Hình học + sweepline 2

Nhiệm vụ 5.9. Test Hình học + sweepline 3

Gợi ý:

• Phiên bản đơn giản: hackerearth

• Phiên bản khó: the-hyp0cr1t3 GitHub