- CHUYÊN ĐỀ DUYÊN HẢI MÔN TIN HỌCGIẢI CÁC BÀI TOÁN HÌNH HỌC TRONG TIN HỌC MỤC LỤCI. - Mở đầu II. - Những công thức hình học cơ bản III. - Một số bài tập áp dụng Bài 1: Dãy hình chữ nhật lồng nhau Bài 2: Tính giao điểm Bài 3: Đổi đất. - Các bài tập tham khảo thêm Bài 1: Tổng véctơ Bài 2: Đếm hình chữ nhật Bài 3: Điểm và đa giác Bài 4. - Xây dựng đường Bài 5: Nông trại V. - Kết luận CHUYÊN ĐỀ GIẢI CÁC BÀI TOÁN HÌNH HỌC TRONG TIN HỌCI. - Mở đầu Các bài toán hình học trong tin học rất đa dạng và phong phú. - Mỗi bài cóthể kết hợp nhiều thuật toán cơ bản khác nhau ở các chuyên đề như Quy hoạchđộng, Đồ thị,… kết hợp với các công thức hình học giải tích cơ bản cho ra kếtquả tối ưu của bài toán. - Trong chuyên đề này tôi trình bày một số bài toán hìnhhọc có các cách kết hợp các thuật toán khác nhau.II. - Những công thức hình học cơ bản1. - Khoảng cách giữa 2 điểm A(x1,y1), B(x2,y2) trong mặt phẳng d. - y1 y 2) 22. - Khoảng cách từ một điểm M(x0,y0) đến đường thẳng d có phương trìnhtổng quát ax + by + c = 0: ax0 by0 c h a 2 b23. - Phương trình đường thẳng đi qua hai điểm A(x1,y1), B(x2,y2): x x1 y y1 x 2 x1 y 2 y1 đưa về dạng tổng quát: (y1 - y2)x + (x2 - x1)y + (x1y2 - x2y1. - Vị trí tương đối giữa hai đường thẳng d1: a1x + b1y = c1, d2: a2x + b2y = c2 Ta tính các định thức: D = a1b2 - a2b1. - Nếu (D = 0) và (Dx = 0) và (Dy = 0) thì d1 và d2 trùng nhau. - Nếu (D =0) và ((Dx 0) hoặc (Dy 0)) thì d1 song song với d2. - Nếu D 0 thì hai đường thẳng cắt nhau tại x=Dx/D. - Hai đoạn thẳng giao nhau Cho hai đoạn thẳng được xác định bởi d1: A(x1,y1), B(x2,y2), d2: (x3,y3), D(x4,y4).a, Cách 1 3 Tìm giao điểm của 2 đường thẳng AB và CD, sau đó kiểm tra xem giaođiểm có thuộc đồng thời cả hai đoạn thẳng AB và CD hay không.b, Cách 2 Xây dựng hai phương trình đường thẳng đi qua AB (F) và CD (G). - NếuAB cắt CD thì C, D nằm về hai phía của đường thẳng AB tức làF(x3,y3)*F(x4,y4)
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt