Tài liệu ứng dụng vecto vào giải quyết một số bài toán hình học trong tin học.

SỞ GIÁO DỤC VÀ ĐÀO TẠO NAM ĐỊNH TRƢỜNG TRUNG HỌC PHỔ THÔNG CHUYÊN LÊ HỒNG PHONG NAM ĐỊNH SÁNG KIẾN DỰ THI CẤP TỈNH BÁO CÁO SÁNG KIẾN ỨNG DỤNG VECTO VÀO GIẢI QUYẾT MỘT SỐ BÀI TOÁN HÌNH HỌC TRONG TIN HỌC Tác giả: Đỗ Thị Minh Hường Trình độ chuyên môn: Thạc sỹ Chức vụ: giáo viên Nơi công tác: trường trung học phổ thông chuyên Lê Hồng Phong Nam định Nam định, ngày 15 tháng 5 năm 2015 1 1.Tên sáng kiến: Ứng dụng vecto vào giải quyết một số bài toán hình học trong tin học. 2. Lĩnh vực áp dụng sáng kiến: Các trƣờng THPT chuyên dạy cho học sinh chuyên và tập huấn cho học sinh dự kỳ thi học sinh giỏi Quốc gia môn Tin học Lớp 12. 3. Thời gian áp dụng sáng kiến: từ năm 2010 đến 2015 4.Tác giả: Họ và tên: Đỗ Thị Minh Hƣờng Năm sinh: 1973 Nơi thường trú: 9/581 đƣờng Trƣờng Chinh phƣờng Hạ Long, thành phố Nam Định Trình độ chuyên môn: Thạc sỹ Chức vụ công tác: giáo viên Nơi làm việc: trƣờng THPT chuyên Lê Hồng Phong Địa chỉ liên hệ: 9/581 đƣờng Trƣờng Chinh, phƣờng Hạ Long thành phố Nam Định. Điện thoại: 0983.846.411 5. Đơn vị áp dụng sáng kiến: Tên đơn vị: trƣờng THPT chuyên Lê Hồng Phong Địa chỉ: 76 Vị Xuyên, thành phố Nam Định Điện thoại: 0350.3640.297 2 BÁO CÁO SÁNG KIẾN I. ĐIỀU KIỆN HOÀN CẢNH TẠO RA SÁNG KIẾN Trong toán học có rất nhiều bài toán nếu dùng các giải pháp thông thƣờng để giải quyết có thể rất dài và phức tạp, nhƣng khi dùng vecto vào giải quyết thì vấn đề trở nên đơn giản và rất ngắn gọn. Chính vì vậy khi dạy chuyên đề hình học cho học sinh khối chuyên tin tôi thiết nghĩ tại sao không dùng vecto vào giải quyết cho lập trình một số bài toán hình học cho học sinh. Những vấn đề này trong toán học các em đều đƣợc học trong chƣơng trình phổ thông, nếu giúp các em có thể áp dụng những vấn đề này vào tin học thì chắc chắn việc đƣa ra thuật toán và cách giải cho nhiều bài toán sẽ trực quan và cài đặt sẽ dễ dàng thuận lợi. II. MÔ TẢ GIẢI PHÁP 1. Mô tả giải pháp trước khi tạo ra sáng kiến Khi dạy cho học sinh khối chuyên tin tôi thấy khả năng về toán của các em hầu hết đều không tốt và đặc biệt là chƣa có phƣơng pháp học kế thừa những đơn vị kiến thức đã học. Tất cả những vấn đề giáo viên đƣa ra hoặc đọc tài liệu hầu nhƣ các em đều cho là mới tinh và chƣa biết tìm hiểu những vấn đề này đƣợc xây dựng và kế thừa từ những đơn vị kiến thức nào đã học để suy luận và từ đó có thể đƣa ra những vấn đề mới đƣợc tổng hợp từ những vấn đề đã biết. Chính vì vậy, tôi xây dựng hệ thống chuyên đề về vecto đƣợc biết trong toán học và phƣơng pháp biểu biễn trong tin học các yếu tố hình học trong lập trình dƣới dạng kế thừa các đơn vị kiến thức đã biết, giúp học sinh có thể đọc, hiểu và đặc biệt là làm quen phƣơng pháp biết kế thừa những kiến thức cũ để xây dựng lý thuyết mới và đặc biệt là giúp các em có một phƣơng pháp giải quyết một số bài toán hình học trong kì thi học sinh giỏi các cấp. 2. Mô tả giải pháp sau khi có sáng kiến 3 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”. A. Một số khái niệm cơ bản 1. Hệ tọa độ Đề các Trong mặt phẳng, cho hệ tọa độ Đề các Oxy có i , j lần lƣợt là hai vecto đơn vị trên trục Ox, Oy. Chiều quay từ i tới j là chiều thuận (ngƣợc chiều kim đồng hồ). 2. Tọa độ - Trong mặt phẳng tọa độ Oxy, cho hai vectơ u  xu ; yu  ; v  xv ; yv  và k là một số thực. Khi đó ta có các kết quả trong toán học (hình tọa độ trong mặt phẳng ở lớp 10 PTTH): +) i 1;0 ; j  0;1 +) u  v   xu  xv ; yu  yv   xu  xv  yu  yv +) u = v   +) k.u   k.xu ; k. yu  +) Độ dài vectơ u  xu 2  yu 2 - Các công thức về tọa độ điểm: Cho điểm A(xA; yA) ; B(xB; yB) +) Tọa độ vectơ AB   xB  xA ; yB  yA  x x y y +) I là trung điểm AB thì tọa độ I  A B ; A B   2 4 2  +) Độ dài đoạn thẳng AB =  xA  xB    y A  yB  2 2 - Hai phép toán đối với hai vecto +) Tích chấm (tích vô hƣớng) của hai vecto: Cho hai vecto u và v , tích vô hƣớng của hai vecto u và v , đƣợc ký hiệu là u . v đƣợc tính bằng tích độ dài của hai vecto u và v nhân với cosin của góc xen giữa hai vecto đó (góc này là góc không định hƣớng có số đo nằm trong đoạn từ 0 đến ).   u.v  u . v .cos u , v Nếu tọa độ của u   xu ; yu  ; v   xv ; yv  thì u.v  xu .xv  yu . yv Từ công thức này ta có thể tính đƣợc cosin của góc tạo bởi giữa hai vecto u và v   cos u , v  u.v xu .xv  yu . yv  x  yu2 . xv2  yv2 2 u u.v +) Góc định hƣớng giữa hai vecto: Cho hai vecto u và v , góc định hƣớng giữa hai vecto u và v là góc lƣợng giác giữa hai vecto này, dấu của góc là dƣơng nếu chiều từ u đến v là ngƣợc chiều kim đồng hồ và mang dấu âm theo chiều ngƣợc lại. +) Tích chéo của hai vecto: Cho hai vecto u và v , tích chéo của hai vecto u và v , đƣợc ký hiệu là u  v đƣợc tính bằng tích độ dài của hai vecto u và v nhân với sin của góc xen giữa hai vecto đó (góc này là góc định hƣớng có số đo nằm trong đoạn từ - đến ).   u.v  u . v .sin u , v Nếu tọa độ của u   xu ; yu  ; v   xv ; yv  thì u  v  xu . yv  xv . yu  xu xv yu yv Từ công thức trên ta có thể tính đƣợc sin của góc định hƣớng giữa hai vecto u và v sin   uv u.v  xu . yv  xv . yu x  yu2 . xv2  yv2 2 u 5 +) Ứng dụng của tích chéo trong khảo sát chiều: Giả sử ta đi từ điểm A sang điểm B theo một đƣờng thẳng và đi tiếp sang C theo đƣờng thẳng, khi đó ta xét: T = AB  BC  AB . BC .sin  , trong đó  là góc định hƣớng giữa hai vecto AB và BC . Ta thấy dấu của T phụ thuộc vào dấu của góc . - Nếu T < 0 thì chỗ rẽ tại B là “rẽ phải” - Nếu T > 0 thì chỗ rẽ tại B là “rẽ trái” - Nếu T = 0 thì ba điểm A, B, C thẳng hàng. 3. Đổi hệ trục tọa độ Bài toán: Cho hai hệ tọa độ trực chuẩn trên mặt phẳng (O; i ; j ) và (O’; i ' ; j ' ). Giả sử điểm M có tọa độ M(x; y) đối với hệ tọa độ (O’; i ' ; j ' ). Hãy xác định tọa độ điểm M đối với hệ tọa độ (O; i ; j )? Giải Giả sử trong hệ tọa độ (O; i ; j ), điểm O’ có tọa độ O’(p, q), vecto i ' =(a; b); j ' = (c; d) Khi đó ta có: OO '  p.i  q. j i '  a.i  b. j j '  c.i  d . j Điểm M có tọa độ (x; y) đối với hệ toạ độ (O’; i ' ; j ' ), khi đó ta có: O ' M  x.i '  y. j ' Do đó    OM  OO '  O ' M  p.i  q. j  x.i '  y. j '  p.i  q. j  x. a.i  b. j  y. c.i  d . j    ax  cy  p  .i  bx  dy  q  . j Suy ra tọa độ điểm M đối với hệ toạ độ (O; i ; j ) là M(ax+by+p; bx+dy+q) Khi đó ta có công thức đổi tọa độ như sau: Giả sử trong hệ tọa độ (O; i ; j ) điểm O’(p; q); i ' =(a; b); j ' =(c; d) và M( x; y ) . 6  x  a.x  c. y  p Trong hệ tọa độ (O’; i ' ; j ' ) điểm M(x; y) và thì   y  b.x  d . y  q 4. Xây dựng công thức biến đổi tọa độ Trong hình học phẳng có các phép biến hình nhằm biến đổi từ hình này sang hình khác đồng dạng với nó. Các phép biến hình này rất quan trọng trong việc thiết kể các bài toán liên quan đến hình trong tin học. Ở đây ta nghiên cứu cách xây dựng các công thức biến đổi tọa độ của các phép biến hình này. Trong hệ tọa độ đề các (O; i ; j ), chọn điểm I(1; 0) và J(0; 1). Với phép đồng dạng f, ta thực hiện f trên ba điểm O, I, J để nhận đƣợc ba ảnh tƣơng ứng của chúng theo thứ tự là O’, I’, J’. Từ đó xác định tọa độ điểm O’(p; q); vecto i '  O ' I '   a; b  và vecto j '  O ' J '   c; d  . Vì đây là phép biến đổi đồng dạng nên điểm M có tọa độ (x; y) đối với hệ tọa độ (O; i ; j ) thì nó cũng có tọa độ (x; y) đối với hệ (O’; i ' ; j ' ). 4.1. Phép quay Xét phép quay tâm O góc . Phép quay này giữ bất biến điểm O tức là O’(0;0), điểm I(1; 0) biến thành I’(cos; sin), điểm J(0; 1) biến thành J’(sin; cos). Khi đó ta có : O’(0;0) ; O ' I ' = (cos; sin); O ' J ' =(- sin; cos). Áp dụng công thức đổi trục toạ độ ở trên ta có:  x  x.cos   y.sin    y  x.sin   y.cos  - Các trƣờng hợp đặc biệt:  x   y +) Góc  = 900 ta có công thức đổi trục là:   y  x  x   x +) Góc  = 1800 ta có công thức đổi trục là:   y   y 4.2. Phép tịnh tiến 7 Xét phép tịnh tiến theo vecto (a; b). Phép tịnh tiến này biến điểm O(0; 0) thành điểm O’(a; b), điểm I(1; 0) biến thành điểm I’(a+ 1; b) và điểm J(0;1) biến thành điểm J’(a; b+1) Khi đó ta có: O’(a; b) ; O ' I ' = (1; 0); O ' J ' = (0;1) x  x  a Áp dụng công thức đổi trục tọa độ ta có   y  y  b 5. Biểu diễn các yếu tố trong hình học 5.1 Đường thẳng Ta thấy trong hình học phẳng, một đƣờng thẳng có nhiều cách biểu diễn. Nhƣng để biểu diễn yếu tố này trên máy tính ta sẽ chọn một số cách biểu diễn sau: - Dạng đƣờng thẳng có hệ số góc: phƣơng tình đƣờng thẳng có dạng y = ax + b. Do đó để biểu diễn đƣờng thẳng này ta chỉ cần quan tâm tới cặp 2 số a và b. - Dạng phƣơng trình tổng quát ax + by + c = 0. Để biểu diễn dƣới dạng này đƣờng thẳng đƣợc đặc trƣng bởi bộ 3 hệ số a, b, c trong đó vecto pháp tuyến là n = (a; b). - Dạng ax + by = c - một dạng của tổng quát đã đƣợc biến đổi. Để biểu diễn ở dạng này ta chỉ cần quan tâm tới một vecto pháp tuyến n = (a; b) và một điểm P(x; y) thuộc đƣờng thẳng. Khi đó ta có thể viết đƣợc phƣơng trình đƣờng thẳng bằng cách sau: n.OP = (a; b).(x; y) = ax+by = c. - Dạng tham số: ta chỉ cần quan tâm tới một vecto chỉ phƣơng u =(a; b) và một điểm P là điểm thuộc đƣờng thẳng. Việc chuyển đổi từ phƣơng trình dạng tham số sang tổng quát hoặc ngƣợc lại trong toán học đã biết. 5.2. Đoạn thẳng: Để biểu diễn đoạn thẳng ta quan tâm tới hai đầu mút của đoạn 8 5.3. Tia: Để biểu diễn tia Ax, ta quan tâm tới gốc A và 1 vecto chỉ hƣớng của tia hoặc có thể biểu diễn bởi gốc A và một điểm B nằm trên tia. 5.4. Đa giác: Đa giác là một đƣờng gấp khúc khép kín. Để biểu diễn đa giác trên máy tính ta lƣu một dãy các đỉnh liên tiếp nhau. B. Một số bài toán cơ bản 1. Cài đặt một số phép toán cơ bản trên vecto Uses math; Type Real = Extended; Tpoint = record x, y : real; End; Tvecto = Tpoint; Const eps : real=1e-3; ----Phép toán tích chéo của hai vecto--Operator ><(const u, v : fload):fload; Begin Result:=u.x*v.y – u.y*v.x; End; ----Kiểm tra hai số thực bằng nhau---Function realEq(const a, b: real):boolean; Begin RealEq:=abs(a – b)<=eps; End; ----Kiểm tra hai điểm trùng nhau ---9 Function EqPoint(const A, B: TPoint):boolean; Begin EqPoint:=realEq(A.x,B.x) and realEq(A.y,B.y); End; 2.Biểu diễn tuyến tính Bài toán 1: Cho ba vecto a , b và c . Tìm cặp số (p; q) để c  p.a  q.b ? Giải quyết Giả sử trong hệ tọa độ Oxy, tọa độ của ba vecto lần lƣợt là a  a1; a2  ; b   b1; b2  ; c   c1; c2  a1 p  b1q  c1 (I) a2 p  b2 q  c2 Khi đó c  p.a  q.b   Do đó vấn đề cần giải quyết của bài toán trở thành tìm nghiệm của hệ (I) với ẩn là p và q. Để giải quyết vấn đề này ta tính ba định thức D Dp  Dq  a1 a 2 b1 b2 c1 c2 b1 b2 a1 a 2 c1 c2  ab  cb  ac Vì thế sẽ có ba trƣờng hợp sau: Dp   p  D , đây chính là cặp số (p; q) duy nhất +) D  0 : hệ có nghiệm duy nhất   q  Dq  D thỏa mãn yêu cầu bài toán. +) D = 0 , khi đó hai vecto a , b cùng phƣơng - Dp= Dq = 0 thì hệ vô số nghiệm, khi đó c cùng phƣơng với cả hai vecto a , b . Khi đó hệ có nghiệm (p; q) =(Nan; Nan) 10 - Dp  0 hoặc Dq  0 thì hệ vô nghiệm, khi đó c không cùng phƣơng với hai vecto a , b . Khi đó hệ có nghiệm (p; q) = (Inf; Inf) Cài đặt function var bdtt(const a, b, c : tvecto):Tvecto; d : float; begin D:=a>< b; result:=vector((c>0 , p[0;1] 6. Tam giác - Biểu diễn tam giác: thông thƣờng tam giác đƣợc xác định bởi ba đỉnh tam giác. - Diện tích tam giác: Ta có thể dùng một số công thức sau: a.hb 2 ab sin C +) Tính theo hai cạnh và góc xen giữa: S  2 +) Tính theo đƣờng cao và cạnh đáy: S  +) Tính theo ba cạnh (công thức Herong): S  p  p  a  p  b  p  c  , với p là nửa chu vi. +) Tính theo tích chéo: S  AB  AC (7a) 2 12 +)Với tọa độ ba đỉnh A(xA; yA); B(xB; yB); C(xC; yC) thì công thức (7a) có thể viết theo tọa độ S   xB  xA  yC  y A    xC  xA  yB  y A  (7b) 2 7.Đa giác 7.1. Diện tích đa giác Bài toán 5: Trên mặt phẳng với hệ tọa độ Đêcác vuông góc, cho đa giác P= P1P2…Pn , trong đó các điểm Pi có tọa độ tƣơng ứng là (xi; yi). Tính diện tích đa giác P? Giải quyết * Ta bổ sung thêm điểm P0 ≡ Pn và điểm Pn+1 ≡ P1. Khi diện tích đa giác P đƣợc tính bằng công thức S 1 2 n  OPi  OPi 1  i 1 1 2 n  x i 1 i 1  xi 1  yi Ta chứng minh công thức trên với hình vẽ minh họa một đa giác có bốn đỉnh P1, P2, P3, P4. P4 P2 P3 P1 O Dựa vào hình vẽ ta thấy S  SOP P  SOP P  SOP P  SOP P 1 2 2 3 3 4 4 1 Mà theo phần trên (diện tích tam giác) ta thấy +) Quay vecto OP1 tới vecto OP2 là hƣớng thuận nên theo công thức (7a) thì SOP1P2 mang dấu âm +) Tƣơng tự nhƣ vậy SOP P mang dấu âm con SOP P và SOP P mang dấu 2 3 3 4 4 1 dƣơng. Khi đó, ta thấy diện tích đa giác là S= 1 1 n  OP1  OP2  OP2  OP3  ...  OPn  OPn 1    OPi  OPi 1  (8a) 2 2  i 1    13 - Khi các đỉnh của đa giác đƣợc đánh theo chiều kim đồng hồ thì bằng lập luận tƣơng tự ta cũng có công thức tính diện tích đa giác là: 1 n  S     OPi  OPi 1  (8b) 2  i 1  Tóm lại, tổng quát trong trƣờng hợp các đỉnh của đa giác đƣợc đánh theo chiều thuận hay nghịch thì ta đều có thể tính diện tích đa giác P bằng công thức sau: S  1 2 n  OP  OP i 1 i i 1 (8c) * Ta sẽ chứng minh công thức tính diện tích đa giác theo tọa độ các đỉnh. Vì điểm Pi có tọa độ tƣơng ứng là (xi; yi) nên các vecto OPi có tọa độ tƣơng ứng là (xi ; yi), dựa vào công thức tích chéo, ta có 1 n   xi yi1  xi1 yi  2 i 1 1   x1 y2  x2 y1  x2 y3  x3 y 2  x3 y4  x4 y 3  ...  xn y1  x1 yn  2 1   xn y1  x2 y1  x1 y2  x3 y 2  ...  xn 1 yn  x1 yn  2 1 n    xi 1  xi 1  yi (8d) 2 i 1 S 7.2. Kiểm tra điểm nằm trong đa giác Bài toán 6: Trên mặt phẳng với hệ tọa độ Đêcác vuông góc, cho đa giác P= P1P2…Pn và một điểm A. hãy cho biết điểm A có nằm trong đa giác hay không? Giải quyết - Nếu điểm A thuộc một cạnh của đa giác thì kết luận A nằm trong đa giác. - Nếu không thì: +) Từ A xác định một tia gốc A không đi qua đỉnh nào của đa giác, ta gọi tia này là tia AB. Có nhiều cách chọn tia này, ví dụ nhƣ chọn ngẫu nhiên n+1 tia đôi một khác nhau, khi đó chắc chắn sẽ có một tia không đi qua đỉnh nào của đa giác. Tuy nhiên, trên thực tế, phƣơng pháp hiệu quả hơn đƣợc áp dụng 14 là: sinh ngẫu nhiên một tia, nếu tia đó đi qua một đỉnh của đa giác thì sinh ngẫu nhiên một tia khác và thử lại. +) Nếu tia AB cắt cạnh đa giác một số lẻ lần thì điểm A nằm trong đa giác, ngƣợc lại thì điểm A nằm ngoài đa giác. C. Bài tập Bài 1: Triangle and point Cho tam giác ABC và 1 điểm M không nằm trên cạnh của tam giác. Yêu cầu: Hãy viết chƣơng trình tính số lớn nhất R sao cho vòng tròn tâm M, bán kính R không cắt bất cứ cạnh nào và không chứa tam giác ABC. Input: Ghi trong file TRIANGLE.INP - Dòng đầu tiên ghi 6 số thực là toạ độ ba đỉnh của tam giác Ax Ay Bx By Cx Cy - Dòng thứ hai ghi toạ độ điểm M : Mx My Các số thực đƣợc viết với 1 chữ số thập phân, cách nhau bởi 1 dấu cách Output: ghi ra file TRIANGLE.OUT gồm 1 số duy nhất R làm tròn đến 1 chữ số sau dấu phảy. Ví dụ TRIANGLE.OUT TRIANGLE.INP 0.2 1.1 0.0 0.3 2.0 0.0 4.0 0.0 2.0 Thuật toán Kiểm tra xem điểm M nằm ở đâu +) Điểm M nằm trong tam giác thì R = min(d(M, AB), d(M, AC), d(M, BC)) +) Nếu điểm M nằm ngoài tam giác thì có khả năng sau 15 A Ví dụ điểm M nằm ngoài về phía đối diện với điểm A bị chia cắt bởi đƣờng thẳng BC B C M2 M1 - Ở vị trí M1 bị giới hạn bởi cạnh AB M3 kéo dài và tia vuông góc với BC tại B: thì R = M1B - Ở vị trí M2 bị giới hạn bởi hai tia tia thứ nhất vuông góc với BC tại B và tia thứ hai vuông góc với BC tại C: thì R = d(M2, BC) - Ở vị trí M3 bị giới hạn bởi cạnh AC kéo dài và tia vuông góc với BC tại C: thì R = M3C Tƣơng tự nhƣ vậy với hai trƣờng hợp còn lại. Cài đặt Uses math; const finp='triangle.inp'; fout='triangle.out'; var fi,fo:text; n,i,test:longint; xa,ya,xb,yb,xc,yc,xm,ym,r:extended; function kc(x1,y1,x2,y2:extended):extended; begin exit(sqrt(sqr(x2-x1)+sqr(y2-y1))); end; function ccw(x1,y1,x2,y2,x3,y3:extended):extended; var a1,b1,a2,b2:extended; begin 16 a1:=x2-x1; b1:=y2-y1; a2:=x3-x2; b2:=y3-y2; exit(a1*b2-a2*b1); end; function kt:boolean; var a,b,c:extended; begin a:=ccw(xa,ya,xb,yb,xm,ym); b:=ccw(xb,yb,xc,yc,xm,ym); c:=ccw(xc,yc,xa,ya,xm,ym); if ((a>0)and(b>0)and(c>0))or((a<0) and(b<0)and(c<0))then exit(true) else exit(false); end; function tinh(x1,y1,x2,y2:extended):extended; var a1,a2,b1,b2,c1,c2,x3,y3,a,b,c:extended; begin a1:=x2-x1;b1:=y2-y1;c1:=a1*xm+b1*ym; a2:=b1;b2:=-a1;c2:=a2*x1+b2*y1; y3:=(c1*a2-c2*a1)/(b1*a2-b2*a1); x3:=(c1-b1*y3)/a1; a:=kc(x3,y3,xm,ym); b:=kc(x1,y1,xm,ym); c:=kc(x2,y2,xm,ym); 17 if kc(x1,y1,x3,y3)+kc(x2,y2,x3,y3)kc(x1,y1,x2,y2)<=0.000000001 then exit(a) else exit(min(b,c)); end; procedure lam; var a,b,c:extended; begin if kt then begin a:=tinh(xa,ya,xb,yb); b:=tinh(xb,yb,xc,yc); c:=tinh(xa,ya,xc,yc); r:=min(a,min(b,c)); end else begin a:=tinh(xa,ya,xb,yb); b:=tinh(xb,yb,xc,yc); c:=tinh(xa,ya,xc,yc); r:=min(a,min(b,c)); end; write(fo,r:0:1); end; begin assign(fi,finp);reset(fi); assign(fo,fout);rewrite(fo); readln(fi,xa,ya,xb,yb,xc,yc); 18 readln(fi,xm,ym); lam; close(fi);close(fo); end. Bài 2: Vườn cây (đề thi chọn học sinh giỏi khu vực duyên hải và đồng bằng bắc bộ năm học 2013-2014) Bờm vừa thằng cƣợc Phú Ông và phần thƣởng là lấy tất cả các cây gỗ sƣa trong vƣờn của Phú Ông. Thấy Phú Ông thẫn thờ vì mất cây, Bờm liền đƣa cho Phú Ông một sợi dây và nói: “Ông hãy chọn một số cây, những cây còn lại tôi sẽ lấy đi, chú ý rằng, sau khi tôi lấy đi thì những cây còn lại phải bao đƣợc bằng sợi dây này”. Phú Ông đồng ý ngay và tìm cách chọn cây sao cho giữ lại đƣợc nhiều cây nhất. Giả sử vƣờn cây của Phú Ông có n cây và coi mỗi cây nhƣ một hình tròn trên mặt phẳng, các cây có cung bán kính r, cây thứ i có tọa độ tâm (xi, yi). Khu vƣờn của Phú Ông Yêu cầu: Cho d là độ dài sợi dây và tọa độ tâm của n cây, các cây có bán kính r. Hãy giúp Phú Ông tìm cách chọn để giữ lại nhiều cây nhất. Dữ liệu: Vào từ thiết bị vào chuẩn: Dòng đầu tiên ghi số nguyên dƣơng K là số lƣợng bộ dữ liệu. Tiếp đến là K nhóm dòng, mỗi nhóm tƣơng ứng với một bộ dữ liệu có cấu trúc nhƣ sau: - Dòng thứ nhất ghi ba số nguyên dƣơng d, n và r (d  109 ; r  100) - n dòng tiếp theo, dòng thứ i chứa hai số nguyên xi, yi (|xi|, |yi|  1000). 19 Dữ liệu đảm bảo các hình tròn không giao nhau. Các số trên cùng một dòng đƣợc ghi cách nhau ít nhất một dấu cách. Kết quả: Ghi ra thiết bị ra chuẩn gồm K dòng, mỗi dòng ghi một số nguyên là số lƣợng cây mà Phú Ông có thể giữ lại đƣợc ứng với bộ dữ liệu trong file dữ liệu vào. Sub 1: n <=2 Sub 2: n <=3 Sub 3: n<=4 Sub 4: n<=10 Ví dụ Thuật toán - Duyệt nhị phân các khả năng mà Phú Ông có thể giữ lại số lƣợng cây (giả sử là k) từ n giảm dần về 1. - Với mỗi phƣơng án ta tìm bao lồi bao quanh tâm của k cây và kiểm tra xem tổng độ dài của bao lồi cộng thêm chu vi đƣờng tròn của 1 cây = d: thoả mãn ta tìm đƣợc phƣơng án cần tìm -> kết thúc. Cài đặt const type MAX = 10; fi = ''; fo = ''; eps = 1e-9; Point = record x, y: extended; 20