Tuyển tập bài tập Chuyên Tin 3: Các bài toán Hình học và Tọa độ

• Người hướng dẫn: Hồ Sĩ Đam
• Chuyên ngành: Tin học
• Đề tài: Bài tập Chuyên tin học Quyển 3
• Loại tài liệu: Sách bài tập

Tóm tắt

I. Tổng quan về sách bài tập chuyên tin quyển 3

Sách bài tập chuyên tin quyển 3 là phần quan trọng trong bộ tài liệu chuyên Tin học do nhóm tác giả Hồ Sĩ Đàm, Đỗ Đức Đông, Lê Minh Hoàng, Trần Đỗ Hùng và Nguyễn Thành Hùng biên soạn. Bộ sách được Nhà xuất bản Giáo dục Việt Nam ấn hành, nhằm phục vụ học sinh các trường chuyên, lớp chọn trung học phổ thông và trung học cơ sở. Quyển 3 tập trung vào các bài tập nâng cao, đòi hỏi tư duy thuật toán sâu sắc. Nội dung sách bao gồm hai phần chính: phần bài tập được sắp xếp từ dễ đến khó, và phần hướng dẫn giải chi tiết giúp người đọc tự kiểm tra quá trình học tập. Bộ sách được xây dựng theo định hướng Chương trình của Bộ Giáo dục và Đào tạo, tạo thành hệ thống tài liệu hoàn chỉnh bên cạnh bộ sách lý thuyết tương ứng. Ngoài đối tượng chính là học sinh chuyên tin, sách còn là tài liệu tham khảo hữu ích cho sinh viên đại học, cao đẳng luyện thi Olympic Tin học và lập trình viên quốc tế.

1.1. Mục tiêu và đối tượng sử dụng

Sách bài tập chuyên tin quyển 3 hướng đến nhiều đối tượng người học khác nhau. Đối tượng chính là học sinh các trường chuyên, lớp chọn ở cấp trung học phổ thông và trung học cơ sở đang theo học chương trình chuyên tin. Bên cạnh đó, sinh viên các trường đại học, cao đẳng cũng có thể sử dụng sách để chuẩn bị cho các kỳ thi Olympic Tin học Sinh viên toàn quốc và kỳ thi lập trình viên quốc tế. Mục tiêu cốt lõi là xây dựng nền tảng tư duy thuật toán vững chắc, phát triển kỹ năng giải quyết vấn đề phức tạp. Giáo viên bộ môn tin học cũng tìm thấy trong sách nguồn bài tập phong phú để thiết kế giáo án giảng dạy hiệu quả.

1.2. Cấu trúc và cách trình bày sách

Sách bài tập chuyên tin quyển 3 được tổ chức thành hai phần rõ ràng. Phần I bao gồm tất cả các bài tập trong những chương tương ứng của sách lý thuyết cùng các bài tập bổ sung, được sắp xếp theo thứ tự từ đơn giản đến phức tạp. Phần II là hướng dẫn giải bài tập, có thể là những hướng dẫn chi tiết giúp tìm lời giải hoặc đoạn chương trình chính giúp người đọc hiểu và tự viết chương trình hoàn chỉnh. Đối với một số bài tập, sách chỉ đưa ra đáp án ngắn gọn hướng dẫn ngắn gọn. Các bài tập trong sách được đánh số như trong sách lý thuyết, bài tập bổ sung được đánh ở mục riêng và đánh số tiếp theo.

II. Phân tích nội dung chính sách bài tập chuyên tin 3

Sách bài tập chuyên tin quyển 3 đề cập đến nhiều chủ đề lập trình nâng cao quan trọng trong khoa học máy tính. Các chủ đề chính bao gồm hình học tính toán, lý thuyết trò chơi, tìm kiếm nhị phân và các thuật toán trên đồ thị. Phần hình học tính toán hướng dẫn cách tính độ dài đoạn thẳng nằm trong tam giác, tìm bao lồi của tập điểm và xác định đường thẳng cân bằng. Phần lý thuyết trò chơi giới thiệu hàm Sprague-Grundy, các trò chơi ma trận và chiến lược tối ưu trong trò chơi hai người. Các bài tập về tìm kiếm nhị phân giúp học sinh nắm vững kỹ thuật chia đôi để tìm nghiệm. Đặc biệt, sách còn có các bài toán thực tế như truy tìm tội phạm sử dụng lý thuyết trò chơi, bài toán vật cân bằng thể hiện sự kết hợp giữa hình học và thuật toán. Mỗi chủ đề đều có hệ thống bài tập từ cơ bản đến nâng cao, phù hợp với nhiều trình độ học sinh.

2.1. Hình học tính toán và bao lồi

Hình học tính toán là một trong những chủ đề trọng tâm của sách bài tập chuyên tin quyển 3. Các bài tập yêu cầu tính độ dài đoạn thẳng nằm trong tam giác trên mặt phẳng tọa độ, đòi hỏi kiến thức về tích vectơ và phân hoạch điểm. Kỹ thuật tìm bao lồi được trình bày chi tiết qua thuật toán Graham, sắp xếp các điểm theo thứ tự ngược chiều kim đồng hồ. Bài toán đường thẳng cân bằng sử dụng phương pháp đếm điểm ở hai phía để xác định đường thẳng đi qua nhiều điểm nhất. Khi số điểm lớn, sách giới thiệu phương pháp xấp xỉ kết hợp tìm kiếm nhị phân để tăng hiệu quả tính toán. Các bài tập này rèn luyện khả năng tư duy không gian và kỹ năng lập trình xử lý tọa độ.

2.2. Lý thuyết trò chơi và hàm Sprague Grundy

Phần lý thuyết trò chơi trong sách bài tập chuyên tin quyển 3 giới thiệu các khái niệm nền tảng về trò chơi tổ hợp. Hàm Sprague-Grundy là công cụ quan trọng để xác định trạng thái thắng thua trong các trò chơi hai người lượt đi luân phiên. Các bài tập yêu cầu tính giá trị hàm Sprague-Grundy cho từng vị trí trong trò chơi, từ đó xác định trạng thái ban đầu là N hay P. Sách trình bày bài toán trò chơi ma trận 2x2, tìm điểm yên ngựa và chiến lược tối ưu. Bài toán truy tìm tội phạm minh họa ứng dụng lý thuyết trò chơi trong tình huống thực tế, sử dụng ma trận payoff để tìm chiến lược hỗn hợp tối ưu. Các bài tập này phát triển tư duy logic và khả năng phân tích chiến lược.

III. Phương pháp học tập hiệu quả với sách chuyên tin 3

Để học tập hiệu quả với sách bài tập chuyên tin quyển 3, người học cần xây dựng lộ trình hợp lý và phương pháp khoa học. Trước tiên, nên đọc kỹ phần lý thuyết tương ứng trong bộ tài liệu chuyên Tin học trước khi bắt đầu làm bài tập. Tiếp theo, hãy bắt đầu từ các bài tập đơn giản được đánh số theo thứ tự trong sách, dần dần tăng độ phức tạp. Khi gặp khó khăn, không nên vội xem đáp án mà hãy suy nghĩ kỹ ít nhất mười lăm phút. Phần hướng dẫn giải trong sách được thiết kế linh hoạt: có bài chi tiết, có bài chỉ ghi đoạn chương trình chính. Người học nên cố gắng viết chương trình hoàn chỉnh dựa trên gợi ý trước khi tham khảo lời giải đầy đủ. Việc thực hành thường xuyên trên máy tính là yếu tố không thể thiếu. Nên cài đặt và chạy thử mọi chương trình để hiểu sâu cách thuật toán hoạt động. Ngoài ra, tham gia các nhóm học tập, diễn đàn lập trình sẽ giúp trao đổi kiến thức và giải đáp thắc mắc nhanh chóng.

3.1. Xây dựng lộ trình học từ cơ bản đến nâng cao

Lộ trình học tập sách bài tập chuyên tin quyển 3 cần được thiết kế theo trình tự logic. Giai đoạn đầu tiên, người học nên ôn tập các kiến thức nền tảng về cấu trúc dữ liệu và thuật toán cơ bản. Tiếp theo, chuyển sang các chủ đề cụ thể trong sách như hình học tính toán, bắt đầu từ bài tập tính khoảng cách đơn giản trước khi làm bài bao lồi. Giai đoạn ba tập trung vào lý thuyết trò chơi, nắm vững khái niệm trạng thái thắng thua trước khi tính hàm Sprague-Grundy. Mỗi giai đoạn nên dành thời gian hợp lý, đảm bảo hiểu sâu trước khi tiến lên. Cuối cùng, tổng hợp kiến thức bằng cách giải các bài tập tổng hợp đòi hỏi kết hợp nhiều kỹ thuật.

3.2. Kỹ thuật giải và lập trình thực hành

Kỹ thuật giải bài tập trong sách đòi hỏi sự kết hợp giữa tư duy toán học và khả năng lập trình. Với bài hình học, cần nắm vững phép tính tích vectơ có hướng để xác định vị trí tương đối của điểm và đường thẳng. Bài toán tìm bao lồi yêu cầu hiểu cách sắp xếp điểm và thuật toán quét. Với lý thuyết trò chơi, kỹ thuật quy hoạch động thường được sử dụng để tính hàm Sprague-Grundy cho các trạng thái. Tìm kiếm nhị phân là kỹ thuật quan trọng giúp giảm độ phức tạp thời gian từ O(n) xuống O(log n). Khi lập trình, cần chú ý xử lý đúng các trường hợp biên, kiểm tra dữ liệu đầu vào và tối ưu bộ nhớ. Thực hành thường xuyên trên các nền tảng thi lập trình sẽ nâng cao kỹ năng đáng kể.

IV. Kết luận và ứng dụng thực tiễn của sách chuyên tin 3

Sách bài tập chuyên tin quyển 3 đóng vai trò quan trọng trong việc đào tạo học sinh năng khiếu tin học tại Việt Nam. Hệ thống bài tập phong phú, được sắp xếp khoa học từ cơ bản đến nâng cao giúp người học phát triển tư duy thuật toán toàn diện. Các chủ đề trong sách như hình học tính toán, lý thuyết trò chơi và tìm kiếm nhị phân không chỉ phục vụ thi cử mà còn có ứng dụng rộng rãi trong khoa học máy tính hiện đại. Kiến thức về bao lồi được áp dụng trong đồ họa máy tính, robot học và hệ thống thông tin địa lý. Lý thuyết trò chơi ứng dụng trong trí tuệ nhân tạo, kinh tế học và khoa học chiến lược. Tìm kiếm nhị phân là kỹ thuật cơ bản trong cơ sở dữ liệu và xử lý dữ liệu lớn. Bộ sách cũng là tài liệu quý giá cho việc bồi dưỡng giáo viên, chuẩn bị cho các kỳ thi Olympic tin học cấp quốc gia và quốc tế. Sự đầu tư nghiêm túc vào sách sẽ mang lại nền tảng vững chắc cho tương tương lai công nghệ thông tin.

4.1. Ứng dụng kiến thức trong thi đấu lập trình

Kiến thức từ sách bài tập chuyên tin quyển 3 có giá trị trực tiếp trong các kỳ thi lập trình. Các kỳ thi Olympic Tin học quốc gia và quốc tế thường xuyên xuất hiện bài toán về hình học tính toán, bao lồi và lý thuyết trò chơi. Kỹ năng tìm kiếm nhị phân là nền tảng cho nhiều thuật toán nâng cao trong thi đấu. Bài toán truy tìm tội phạm trong sách tương tự các bài toán lý thuyết trò chơi trong đề thi ICPC và IOI. Việc luyện tập với hệ thống bài tập từ dễ đến khó trong sách giúp học sinh xây dựng phản xạ giải quyết vấn đề nhanh chóng. Đặc biệt, phần hướng dẫn giải chi tiết giúp người học hiểu cách tiếp cận bài toán từ nhiều góc độ khác nhau, kỹ năng quan trọng trong thi đấu thời gian giới hạn.

4.2. Giá trị lâu dài cho phát triển nghề nghiệp

Sách bài tập chuyên tin quyển 3 mang lại giá trị lâu dài vượt ra ngoài phạm vi học đường. Nền tảng tư duy thuật toán được xây dựng từ sách là yếu tố quyết định thành công trong ngành công nghệ thông tin. Các kỹ thuật hình học tính toán được áp dụng trong phát triển game, mô phỏng khoa học và thị giác máy tính. Tư duy lý thuyết trò chơi hỗ trợ trong phân tích kinh doanh, chiến lược tiếp thị và thiết kế cơ chế đấu giá trực tuyến. Khả năng tối ưu hóa thuật toán qua tìm kiếm nhị phân và quy hoạch động là kỹ năng cốt lõi của kỹ sư phần mềm chuyên nghiệp. Nhiều cựu học sinh chuyên tin, từng sử dụng bộ sách này, đã trở thành lập trình viên xuất sắc tại các tập đoàn công nghệ hàng đầu thế giới.

Trích đoạn nội dung tài liệu

HO sT DAM (chri bien) DO DUC DONG - LE MINH HOANG . TRAN o6 HUNC NcuyEru THANH t\\JL.rtEt\ Iftrll utrtrtc \ AA TAI IIEU I CHUYEN TIN H0c I \rl BAI TAP n QUYENJ nHn t, xuAr sANr orno ouc vrEr runvr . HO SI DAM (chri bien) DO DUC DONG - LE MINH HoANG - TRAN Do HUNG , NGUYEN THANH HUNG lA/i TAI IITU l1 CHUYTN TIN HOC \ /'l BAI TAP OUYEI '{3 (Tai bdn ldn thn nhtir) NHA XUAT AAN CIAO DUC VIET NAM ' Lor Nor oAu Bo siich Tditiau chuyanTin hoc - Bdihap Quydn 1,2,3 duoc vidt kdm vdi b6 Tdi li4u chuyanlin hpc - Quydn 1,2,3 ruong rmg dd du-o. G4c tac giA tham gia biOn soan b0 s6ch ld nhirng thdy gi6o dd vl dang d?y o c6c rrudng chuy6n, ldp chon hodc tham gia cdc kh6a bdi dudng thi tin hoc qudc td, bdi dudng gii{o vion tin cho ci{c trudng chuy6n theo chuong trinh crja BO Gir{o duc vd Dho tao, mong mudn xAy dung du-o. c c6c tdi 1i0u c6 tinh h€ thdng phUc vU t6t cdc ddi tuong thuoc llnh vuc chuy€n tin hoc. C6c cudn Tdi li4u chuyan Tin hoc - Bdi tdp ddu c6 cdu trfrc nhu nhau, g6m hai phdn: Phdn I - Bii tQp bao g6m tat ch cdc bei mp rrong nhfrng chuyOn dd cira s6ch Tdi Hau chuyan Tin hoc fiong rlng vh c6c bdi mp bd sung, duoc sap xdp tD d0 den kh6, til don gi6n ddn phrlc tap, Phdn II - Hudng dAn giii bii tAp c6 the IA nhrrng huong ddn chi tidt dd girip ban doc tim duoc ldi giii hoac chi ld doan chuong trinh chinh girip ban doc hidu vd tim du-o. c ldi giii hoac chuong trinh ho)n chinh dd tham khio. Ddi vdi m6t sd bli tap th) c5 thd chi ld d5p 6nhay huong d6n ngin gon. Hai bo s6'ch Tdi liaw chuyan Tin hoc vd, Tdi liau chuyan Tin hoc - Bdi tdp tao thhnh h€ th6ng tdi liOu kh6 hodn chinh theo dinh huong Chuong trinh ciic chuy€n d€ chuyOn tin hoc dd duoc Bd Gir{o duc v}r Ddo tao ban h}rnh. Do vdy cDng vdi b6 s6ch Tdi li0u chuy0n Tin hoc, b6 sSch Tdi liAu chuyAn Tin hoc - Bdi ttlp sd ld tdi liOu thiet thuc phuc vu cho gi6o viOn, hoc sinh c6c trudng chuyOn, l6p chon ci Trung hoc phd thOng vd Trung hoc co s&. Ngodi ra, b6 silch cdn lh tii lieu tham khdo bd ich cho vi€c tap huan sinh viOn cdc trudng Dai hoc, cao d&ng rham gia ciic k) thi olympic Tin hoc Sinh viOn Tobn quoc vd Ki rhi lap rrinh vi0n eudc te. Ltru ! khi sft dqng bQ sdch: cdc bdi tap ffong b6 s6ch ndy du,o.c ddnh sd nhu trong sdch li thuydt; c6c bhi tap bd sung duo. c dd & muc ri€ng vd drinh sd tidp rheo. \Iac dD cdc tdc gi6 vd Ban.biOn tap dd cd gSng hobn rhiOn nhung ch6c chSn b0 sdch cdn nhidu thidu s6t, c6c tdc gia mong nhan duoc nhidu f kien ddng g6p dd sdch s€ hodn thiOn hon, phuc vq ban doc duoc hi6u qu6 hon. Cdc g6p i,xin giri vd: BanTodn-Tin, Cdng ry t'o pldn Dich vu xuat bdn Gido duc Hd N6i- Nhd xudT bcinGido ducVi€t Nam, lSTB,GicingVd, Hd NOi. C6c tirc gih 1 tl I X r1 C p V t I 8. Tr In ca. d6 Or ph, Vf t-- I-T t; tq l- t Qro" Bei t+p cHUYnx on 8. HiNH Hoc rixu roAx 8. Tim d0 dai doqn ttring nim trong tam gi6c Tr€n m[t phing cho tam gi6c ABC vd do4n tning DE. Tinh d6 ddi cira phAn doan thing DE nim trong tam gi6c. Input: TQp BAI0I_C8.INP g6m hai dong: Dong thri nhAt c6 s6u s6 thuc XA, yA, XB, yB, Xc, yc. lAn luot tung cdp ld toa dO tucrng fng cira ba dinh A, B vd C. Dong thf'hai ld b6n s6 thuc XD, yD, Xe, yE lin lugt hrng cdp ld toa d0 hai di6m D vd E. (-) output: TOp BAI0I_c8.our chi c6 m6t dong duy nh6t ghi so thuc ld dq dai phAn doan thing DE nim trong tam gi6c ABC. Vi dq: BAIOl CB. ]NP BAIOl CB. Tim di6n tich phan chung c0a hai tam gi6c Tr€n mdt phang cho hai tam gi6c. Tinh didn tich ph6n chung cria hai tam gi6c d6. Input: TQp BAI02_C8.INP g6m hai dong, m6i dong c6 s6u s6 thuc lAn lugt ttmg cflp ld toa dQ tuong ring cira ba dinh cira mOt tam gi6c. c6c toa d0 c6 gi6 tri tuyQt eOi tnOng vuot qu6 l0r.ouT chi c6 mQt dong duy nhAt ghi s6 thuc ld di€n tfch phAn chung cira hai tam gi6c ndy (chinh x6c dr5n l0-'). vf dg: CB.\'€tr khdng cht' dinh gi th1m thi trong sach nay xin ilu'o'c hi€u rdng cac s6 trOn cilng ddng .ivoc ghi c'ach nhau it nhtit m6t diiu cach. Tinh diQn tich phin ph0 b&i N hinh chir nhft I Cho hai hinh chfr nhflt v6i c5c cpnh song song v6i c6c tryc toA dg. M6i hinh cht T nhit x6c dinh bcri to4 dQ hai dinh. Tinh diQn tich phan m[t phang dugc phu boi Si hai hinh chfl nhQt vd diQn tich phdn chung ctra chring' l, Tt bei to6n ndy ta suy ra bdi to6n t6ng qu6t tinh diQn tich phAn phri boi N hinh 8 chf nh0t nhu sau: s€ Tr€n mat phing toa d0 xOy, cho N hinh cht nh4t c6 c6c c4nh song song v6i c6c di tryc toa d0. In a) Tinh diQn tich phAn mflt phing dugc phri bdi N hinh chir nh4t niy. ti( b) Tinh dign tich phAn chung cua N hinh chfr nhit ndy' o Input: TQp BAI03_C8.INP c6 dong diu ghi s6 nguy6n N (1 < N S 10000). Trong da N do.rg ti6p theo, dlng thf i co b6n sO nguy€n Xir, Yir: xtz, Ytz th6 hiCn (xir; yl) ld i Vi toa d0 dinh tr6i-du6i vd (xiil y,z) ld toa d0 dinh ph6i+r€n cria hinh chir nh4t thu t-- (0 < xir < xiz S 30000, 0 ( yit < Yiz<30000)' L_ TQp BAIO3-C8.OUT c6 hai dong tucrng ung ghi k€t qua cau a) vd cdu b); I4 Output: l0 , t . ,l cac so ghl tu oau oong. r\ la t- Vi ds: lo 14 L__: BAIO3 CB. INP BAI03 CB .; 1032 1 m6 1034 Inl aa iir hai di6m xa nhau nh6ttrong N di6m Nr Tr€n mit phing cho N di,5m. Tim hai di6rn xa nhau nh6t trong N di€m d6. <3 Gqi j/: Hai diOm cAn tim ld hai dinh cua da gtitc bao 16i' Ou Input: TQp BAI04_C8.IM c6 ddng dAu ghi s6 nguy€n N (1 S N < 10000); trong N dong thor < < ticp ttreo, ddng thir i c6 hai s6 nguy€n xi, 1li |d toa d0 di€m thir i (0 xi , yi 30000). thur Output: TQp BAI04_C8.OUT ghi khoing c6ch hai ditim xa nhau nhAt chinh x6c Vir t6i 10-4. I-- Vi dq: l4 t^ BAIO4 CB. INP BAIO4 CB . Phdn hoqch N di6m thdrnh K tap c6 duung kinh t6n ntrdt dqt ntin Tr€n m{t phang cho N di€m. Hdy phdn hopch N didm thdnh K tap Sr, S2,., Sr sao cho ducrng kinh lon nhAt cria K tflp ln nho nh6t, trong d6 ducrng kinh ctra tOp Si ld khodng c6ch l<rn nh6t giira c6c cflp di€m thuQc Si. ircn mflt phing cho N diiSm doi mQt kh6c nhau. Hdy tim hai trong N di6m sao cho ducrng thing di qua hai di6m d6 chia mflt phEng thdnh hai phAn md s6 di6m thuQc hai nria mflt phing ch€nh lQch nhau it nh6t. Input TQp BAI06-G8.INP c6 ddng dau eh ro nguyOn N (l s N s 10000). Trong N ddng ti6p theo, dong thri i c6 hai s6 nguy€n xl, y1 ld toq dQ ditim thu i (0 < x; , y, < 30000).oUT ghi to4 d0 hai di6m tim dugc, m6i eiem tr€n mQt dong. Vi du: BAIO6 CB. Tr€n mat phing cho N di6m. Hdy rim tap it nh6t c6c ducrng thing sao cho m6i Cicm tron! N di€m da cho thu6c it nhAt mQt duong thing. Input: TQp BAI07-C8.INP c6 dong dAu ghi s6 nguy€n N (t < N s 10000). Trong N dong ti6p theo, dong thir i c6 hai s6 nguy6n x;, y; lir toa dQ rti6m thf i (0 < x; , yl s 30000). output: TQp BAI07_c8.our c6 dong dAu ti6n ghi so k ld so dudng thing it nhAt thod mdn y€u cAu ae uai. Ti6p theo ld k dong, m6i dong ghi s6 hiqu ciic di6m cirng thu6c m6t ducrng thing. vf du: BAIOT CB. INP BA]07 CB . Noi N di6m thinh m?ng li6n thong Tr0n m[t phing cho N di0m. Hay nOi N di€m thinh mQt m4ng li€n thong bdng c6c doan thing nOi . c[p di6m sao cho t6ng dQ ddi c6c do4n thing dugc n6i h nh6 nhat' 8. tr€n mflt ph6ng cho N hinh cht nh4t c6 c6c c4nh song song v6i hai tryc to4 d0. Hinh thri i x6c dinh boi hai dinh dOi (xi; yi) vi (zi; ti). Toa d0 c6c ditlm ld nguyen, c6 gi6 tri tuyQt eOi nrOng vugt qu6 104. Khi t6 c6c hinh chir nh?t ndy Uing *au xanh, ta nh{n dugc mQt sO phAn m4t phing dugc td xanh. Tinh tOng dO t ddi c6c ducrng bao quanh c6c vr)ng mdu xanh' I Input: TQp BAI09_C8. k Output: TQp BAI09-C8. n Vi dg: v BA]09 CB. INP BAIO9 CB.OUT' d AQ 1 It 0-250 (( -2 -1 1 3 \ 5166 0225 s( L456 hi 3045 L( 1153 o 8. Tim nhin th Tr€n mdt phing cho N do4n thlng (l S N < 1000). Toa dO c6c ddu mirt cua c6c th do4n thing ld c6c s6 nguy6n kh6ng 6m khdng vugt qu6 20000. C6c ducrng thdng ct thu dugc bing c6ch k6o ddi cdc do4n thing d6 cho ludn c6t hai truc toa d0 vd hai giao di6m cirng g6c toa d0 tao thdrnh mQt tam gi6c vu6ng cAn. Kh6ng co hai-doan I ---: z thing ndro giao nhau. i Ta n6i m6t doan thdng ld nhin thtiy dwqc tit g6c toq dQ O, n€u tim ra di6m X t€n * n6 sao cho doan thdng OX kh6ng cat biit cu dogn ndo trong s6 cdc doqn thdng dd cho. Hdy vitit chucrng trinh dtim s6 doun thing nhin th6y tu gr5c toa d0' 8. Input: TQp BAIl0-C8. Dong dAu ti6n chria s6 do4n thing N. M6i m6t trong Di sO N ddng ti€p theo chira b6n sO nguy€n khong 6m Xr, Yr, Xz, Y2, phdn c6ch boi nq dAu c6ch, trong d6 (Xr; Yr) ld toa dQ cua dAu mrit thri nhAt con (Xz; Y2) le toa d0 C; cua dAu mtit thri hai cira do4n th6ng tuong img. dir I Output: TQp BAI10-C8.OUT ghi s6 dopn thing nhin th6y dugc tu g6c to4 dQ' Vi dq: BAIlO CB. [h6i phgc tla gilc Blm vE trdn mflt phing mOt hinh da gi6c t6ng qu6t (ducrng g6p khirc khep kin khdng tu cit) vdi c6c canh song song v6i c6c truc toa d0 vd c6c dinh c6 top dQ nguy€n. Sau d6, v6 ;i Bom dd xo6 mht tdt ctt chc canh thlng dimg (canh song song v6i truc tung) cria da grhc. B4n hdy tim c6ch girip Bdm tinh di6n tich cira da gritc dd vO ban dAu tir nh.irng th6ng tin con l4i. Input: Tpp v[n bin BAII l_cS.