<span class='text_page_counter'>(1)</span><div class='page_container' data-page=1>

<b>PHƯƠNG PHÁP GIẢI TỐN HÌNH HỌC BẰNG NGƠN NGỮ LẬP TRÌNH PASCAL</b>
Tin học và nhà trường
Qua q trình tham gia giảng dạy và bồi dưỡng học sinh giỏi chúng tơi thấy nhiều bài tốn
địi hỏi học sinh phải tìm ra mơ hình tốn học cụ thể từ yêu cầu phức tạp của bài toán.
Thực tế cho thấy những học sinh có khả năng vận dụng kiến thức tốn học vào q trình
phân tích đề bài sẽ nhanh chóng phát hiện được mơ hình tốn học của bài toán và đưa ra
lời giải hợp lý. Việc hướng cho học sinh phát hiện ra những mối liên hệ của bài tốn cần giải
quyết với các kiến thức tốn thơng dụng qua q trình tìm hiểu nội dung bài tốn là khơng
dễ dàng gì. Với mong muốn phần nào giúp học sinh cũng như giáo viên trong việc tìm ra lời
giải cho một số dạng bài toán thường gặp trong chương trình THPT cần giải quyết lập trình
đó là <b>các bài tốn hình học</b>, chúng tơi xin giới thiệu <b>phương pháp giải tốn hình học</b>

<b>bằng ngơn ngữ lập trình Pascal</b> mà chúng tơi đã áp dụng trong q trình giảng dạy.

<b>I. KHÁI NIỆM HÌNH HỌC VÀ CÁC ĐỐI TƯỢNG HÌNH HỌC CƠ BẢN</b>
<b>1. Khái niệm hình học.</b>

Đa số các thuật toán đều tập trung vào văn bản và các con số, chúng được thiết kế và xử lý
sẵn trong phần lớn các mơi trường lập trình. Đối với các bài tốn hình học thì tình huống
khác hẳn, ngay cả các phép toán sơ cấp trên điểm và đoạn thẳng cũng có thể là một thách
thức về tính tốn.

Các bài tốn hình học thì dễ hình dung một cách trực quan nhưng chính điều đó lại có thể
là một trở ngại. Nhiều bài tốn có thể giải quyết ngay lập tức bằng cách nhìn vào một mảnh
giấy nhưng lại địi hỏi những chương trình khơng đơn giản.

Ví dụ: Bài tốn kiểm tra một điểm có nằm trong đa giác hay khơng?

<b>2. Đối tượng hình học cơ bản.</b>

Trong các bài tốn tin học thuộc loại hình học có 3 đối tượng cơ bản là: Điểm, đoạn thẳng

và đa giác.

- Điểm: Được xác định là cặp (x,y) trong hệ toạ độ đề các.

- Đoạn thẳng: Là cặp điểm được nối với nhau bằng một phần của đường thẳng.

- Đa giác: Là dãy các điểm mà 2 điểm liên tiếp nối với nhau bởi đoạn thẳng và điểm đầu
nối với điểm cuối tạo thành đường gấp khúc khép kín.

</div>
<span class='text_page_counter'>(2)</span><div class='page_container' data-page=2>

<b>II. MỘT SỐ PHÉP TỐN CƠ BẢN</b>

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

<b>Bài toán 1: </b>Cho điểm . 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

<b>Phương pháp:</b>

Đặt

- Điểm M thuộc đường thẳng AB khi
- Điểm M thuộc đoạn thẳng AB khi:

<b>- Chương trình:</b>

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

<b>Bài toán 2. </b>Cho 2 đường thẳng có phương trình . Tìm giao

điểm (nếu có) của 2 đường thẳng trên.

<b>Phương pháp:</b>

+ 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)

<b>Chương trình:</b>

</div>
<span class='text_page_counter'>(3)</span><div class='page_container' data-page=3>

điểm (nếu có) của 2 đoạn thẳng

<b>Phương pháp:</b>

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

Bước 2. 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ó.

<b>Chương trình:</b>

<b>Bài tốn 4.</b> Cho tia AM chứa điểm B (khác A) và đoạn thẳng CD

với . Tìm giao điểm (nếu có) của tia AM với đoạn thẳng
CD.

- Phương pháp:

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

Bước 2. 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ó.

<b>Chương trình:</b>

<b>3. Vị trí của điểm so với đa giác</b>

<b>Bài tốn 5.</b> Cho đa giác gồm N đỉnh và điểm M. Xác định vị trí tương đối của

M với miền trong đa giác.
Phương pháp:

Bước 1. Kiểm tra M có thuộc cạnh nào của đa giác hay khơng, nếu có thì kết luận M thuộc
miền trong đa giác và kết thúc

Bước 2. Kẻ MN song song với trục hoành (điểm N có hồnh độ lớn hơn max hồnh độ của
đa giác)

Bước 3. Xác định d là số giao điểm của MN với các cạnh của đa giác. Những trường hợp sau
được coi như là tăng thêm 1 giao điểm:

+ Đỉnh d[i] không thuộc đoạn thẳng MN, đỉnh d[i+1] nằm trên đoạn thẳng MN, 2 đỉnh d[i]
và d[i+2] khác phía so với đường thẳng MN.

+ Đỉnh d[i-1], d[i+2] ngoài đoạn thẳng MN, hai đỉnh d[i] và d[i+1] thuộc đoạn MN, d[i-1]
và d[i+1] khác phía so với đường thẳng MN

</div>
<span class='text_page_counter'>(4)</span><div class='page_container' data-page=4>

<b>PHẦN II. MỘT SỐ DẠNG BÀI TỐN HÌNH HỌC THƯỜNG GẶP</b>
<b>Dạng 1. Mối quan hệ giữa điểm, đoạn thẳng, đa giác.</b>

<b>Phương pháp:</b> Đây là một trong số dạng bài toán hình học đơn giản nhất. Việc giải

bài tốn dạng này chủ yếu sử dụng các kiến thức hình học cơ bản (đã trình bày đầy
đủ trong phần trên)

<b>VD1 Ba điểm thẳng hàng</b>

Cho N điểm, hãy kiểm tra xem có bao nhiêu bộ 3 điểm thẳng hàng.

<b>Input:</b> Cho trong tệp văn bản DL.INP

- Dòng thứ 1 ghi số N

- N dòng tiếp theo, mỗi dòng ghi toạ độ của một điểm.

<b>Output:</b> Ghi vào tệp KQ.OUT chứa một số duy nhất là số bộ 3 điểm thẳng hàng.

</div>
<span class='text_page_counter'>(5)</span><div class='page_container' data-page=5>

<b>VD2. Đường thẳng cắt nhau</b>

Cho n đường thẳng AiBi (1 ≤i ≤n) phân biệt với Ai, Bi là các điểm cho trước. Hãy thơng
báo ra màn hình các cặp đường thẳng đơi một cắt nhau.

Dữ liệu: Cho trong file DL.INP gồm N dịng (N khơng biết trước). Dịng thứ i ghi 4 số
thực xAi yAi xBi yBi. Các số trên cùng một dịng ghi cách nhau ít nhất một dấu cách.

</div>
<span class='text_page_counter'>(6)</span><div class='page_container' data-page=6>

- Mỗi đường thẳng được đặc trưng bởi 3 thông số a,b,c được xác định:

a:=(y1-y2); b:=(x2-x1) ; c:=x1*y2-x2*y1;

- Hai đường thẳng cắt nhau khi: D:=a1*b2-a2*b1 ? 0;
Chương trình:

<b>VD3. Điểm thuộc đa giác.</b>

</div>
<span class='text_page_counter'>(7)</span><div class='page_container' data-page=7>

<b>Dữ liệu:</b> Cho trong tệp Dagiac.inp
+ Dòng đầu là số N

+ N dòng tiếp theo mỗi dòng ghi xi,yi là toạ độ Ai
+ Dòng n+2 ghi 2 số xA và yA

Dữ liệu là các số ngun.

<b>Kết quả:</b> Đưa ra màn hình thơng báo điểm A có nằm trong đa giác hay khơng

Ý tưởng:

- Lưu toạ độ các đỉnh đa giác vào mảng A
- Kiểm tra xem điểm A có trùng với đỉnh đa giác
- Kiểm tra xem điểm A có nằm trên cạnh đa giác

- Tìm giao điểm nếu có của tia Ax (Ax//Ox và Ax hướng theo phần dương trục hoành)
với các cạnh của đa giác. Trường hợp tia Ax chứa đoạn thẳng cạnh đa giác ta xem
như tia Ax có 1 điểm chung với cạnh này. Cụ thể:

+ Giả sử điểm A(x0,y0), chọn điểm B(xb,yb) với xb=x0+1,yb=y0
+ Kiểm tra tia AB có cắt đoạn thẳng CD bằng cách:

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

Tính

a1:=yb-ya; b1:=xa-xb; c1:=ya*xb-xa*yb;
a2:=yd-yc; b2:=xc-xd; c2:=yc*xd-xc*yd;

D:=a1*b2-a2*b1; Dx:=c2*b1-c1*b2; Dy:=a2*c1-a1*c2;

Xác định: Nếu D ≠0 thì toạ độ giao điểm là N(Dx/D,Dy/D) B2. Kiểm tra N có thuộc tia
AM và đoạn thẳng CD hay không.

</div>
<span class='text_page_counter'>(8)</span><div class='page_container' data-page=8>

- Điểm N thuộc tia AB khi có nghĩa là N phải thoả mãn điều kiện:
(xN-xA)(xB-xA) ≥0 và (yN-yA)(yB-yA) ≥0

+ Kiểm tra tia AB chưa cạnh CD hay không bằng cách: (yc=yd)and(yc=yo)
- Đếm số giao điểm, nếu số giao điểm lẻ thì A thuộc đa giác

</div>
<span class='text_page_counter'>(9)</span><div class='page_container' data-page=9></div>
<span class='text_page_counter'>(10)</span><div class='page_container' data-page=10>

<b>VD4. Đếm số điểm có toạ độ nguyên thuộc đa giác</b>

Cho đa giác gồm n đỉnh (x1,y1), (x2,y2), ..., (xn,yn), biết xi và yi(i=1,...,n) là các số
nguyên trong đoạn [-106_,106_{]. Các đỉnh được liệt kê theo thứ tự cùng chiều kim đồng}
hồ.

Viết chương trình tìm số điểm có toạ độ nguyên nằm trong hay trên biên đa giác.

Dữ liệu:Cho trong tệp tin DL.INP.

- Dòng đầu chứa số nguyên duy nhất cho biết số đỉnh.

- Tiếp theo là các dịng, trên mỗi dịng có 2 số ngun cách nhau một khoảng trắng
lần lượt là hoành độ, tung độ các đỉnh đa giác.

Kết quả:Xuất ra màn hình số điểm có toạ độ nguyên nằm trong hay trên biên đa giác
Ý tưởng:

- Tính a,b theo cơng thức:

</div>
<span class='text_page_counter'>(11)</span><div class='page_container' data-page=11>

Dạng 2.Tính diện tích đa giác

Phương pháp:Giả sử cho đa giác có n đỉnh và toạ độ các đỉnh lưu vào mảng a. Để
tính diện tích đa giác ta làm như sau:

Bước 1. Gắn thêm đỉnh phụ:

a[n+1].x:=a[1].x; a[n+1].y:=a[1].y;

Bước 2. Diện tích đa giác tính theo cơng thức:

Lưu ý:Có thể áp dụng cơng thức khác để tính diện tích trong các trường hợp đặc biệt.
- Nếu đa giác là tam giác (n=3) thì diện tích tính theo cơng thức:

</div>
<span class='text_page_counter'>(12)</span><div class='page_container' data-page=12>

- Nếu đa giác là hình trịn có bán kính R thì diện tích là
VD1.Xác định diện tích đa giác

Cho N đa giác lồi A1A2A3...AN-1AN với các đỉnh Ai(xi,yi) có toạ độ nguyên. Hãy tính diện
tích đa giác trên.

Dữ liệu:Cho trong file DL.INP gồm 2 dòng
- Dòng 1: Chứa số nguyên dương N

- Dòng 2: Chứa 2xN số nguyên dương x1y1x2y2...xNyNlà toạ độ các đỉnh của đa
giác. Mỗi số ghi cách nhau một dấu cách.

Kết quả:Xuất ra màn hình diện tích đa giác.
Ý tưởng:

</div>
<span class='text_page_counter'>(13)</span><div class='page_container' data-page=13></div>
<span class='text_page_counter'>(14)</span><div class='page_container' data-page=14>

VD2.Dãy hình chữ nhật

Trong mặt phẳng toạ độ trực chuẩn, cho N hình chữ nhật có các cạnh song song với
trục toạ độ. Mỗi HCN được xác định bởi toạ độ đỉnh dưới bên trái và đỉnh trên bên
phải của nó. Hãy đưa ra dãy các hình chữ nhật theo thứ tự tăng dần diện tích .

Dữ liệu:Cho trong file HCN.inp gồm N+1 dòng.
- Dòng 1. Chứa số N

-Dòng i+1 (1≤i≤N): Ghi 4 số nguyên x1, y1, x2,y2lần lượt là toạ độ đỉnh dưới bên
trái và đỉnh trên bên phải của HCN i. (Các số ghi trên một dịng cách nhau ít nhất một
dấu cách)

Kết quả:Ghi vào tệp HCN.out dãy các hình chữ nhật sau khi sắp xếp.
Ý tưởng:

</div>
<span class='text_page_counter'>(15)</span><div class='page_container' data-page=15>

- Tính diện tích hình chữ nhật theo cơng thức:

- Sắp xếp mảng a tăng dần theo diện tích
<b>Ý tưởng:</b>

<b>Dạng 3. Xác định diện tích phủ bởi các hình chữ nhật</b>

<b>Phương pháp: </b>Giả sử có n hình chữ nhật. Để tính diện tích phủ bởi n hình chữ nhật

ta làm như sau:

Bước 1. Sử dụng a,b lần lượt là các mảng lưu hồnh độ và tung độ các đỉnh hình chữ
nhật (mỗi hình chữ nhật chỉ cần lưu toạ độ 2 đỉnh đối diện qua tâm hình chữ nhật).
Bước 2. Sắp xếp mảng a,b theo thứ tự tăng dần

</div>
<span class='text_page_counter'>(16)</span><div class='page_container' data-page=16>

trong các hình chữ nhật ban đầu thì cộng thêm vào phần diện tích đang cần tìm diện
tích của hình chữ nhật con này.

<b>Ví dụ 1. Diện tích phủ bởi các hình chữ nhật</b>

Trong mặt phẳng toạ độ trực chuẩn, cho N hình chữ nhật có các cạnh song song với
trục toạ độ. Mỗi HCN được xác định bởi toạ độ đỉnh dưới bên trái và đỉnh trên bên
phải của nó. Hãy tính diện tích phần mặt phẳng bị phủ bởi các HCN trên.

<b>Dữ liệu:</b> Cho trong file HCN.inp gồm N+1 dòng.

- Dòng 1: Chứa số N

-Dòng i+1 (1 ≤i ≤N): Ghi 4 số nguyên x1,y1,x2,y2 lần lượt là toạ độ đỉnh dưới bên
trái và đỉnh trên bên phải của HCN i. Các số ghi trên một dịng cách nhau ít nhất một
dấu cách.

<b>Kết quả:</b> Đưa ra màn hình diện tích phần mặt phẳng bị phủ bởi hình chữ nhật trên.

<b>Ý tưởng:</b>

- Lập mảng X[1..2n], Y[1..2n] lần lượt chứa hoành độ, tung độ các hình chữ nhật

- Lưu toạ độ ban đâu các hình chữ nhật vào mảng a

- Sắp xếp mảng X,Y tăng dần

- Lần lượt kiểm tra các hình chữ nhật có toạ độ đỉnh trên bên phải (xi+1,yi+1) và toạ độ
đỉnh dưới bên phải là (xi,yi) với 1 ≤i ≤n-1. Nếu hình chữ nhật này thuộc một trong các
hình chữ nhật ban đầu thì cộng thêm vào phần diện tích đang cần tìm diện tích của
hình chữ nhật con này.

<b>Chương trình:</b>
<b>Ví dụ 2. </b>Phủ S

Trên mặt phẳng tọa độ, một hình chữ nhật với các cạnh song
song với các trục toạ độ được xác định bởi hai điểm đối tâm:
đỉnh góc trên bên trái và đỉnh góc dưới bên phải. Cho N hình

chữ nhật song song với các trục toạ độ. Phủ S của các hình chữ nhật có diện tích nhỏ
nhất chứa N hình chữ nhật đã cho.

<b>Dữ liệu vào:</b> Đọc từ tệp PHUCN.INP có cấu trúc:

- Dòng đầu tiên chứa N (N ≤30);

- Trong N dòng tiếp theo, mỗi dòng ghi 4 số là toạ độ của hai đỉnh đối tâm của một
hình chữ nhật, các số này là các số nguyên có trị tuyệt đối khơng q 100.

</div>
<span class='text_page_counter'>(17)</span><div class='page_container' data-page=17>

- Dịng 1 ghi toạ độ hai đỉnh đối tâm của phủ S các hình chữ nhật

- Dịng 2 ghi diện tích của phần hình S khơng nằm trong hình chữ nhật nào trong N
hình đã cho

- Ý tưởng:

- Xác định hình chữ nhật H nhỏ nhất bao tất cả các hình
chữ nhật ban đầu:

Gọi minx,maxx lần lượt là hoành độ nhỏ nhất và lớn nhất
trong các hồnh độ các đỉnh hình chữ nhật đã cho; miny,

maxy lần lượt là tung độ nhỏ nhất và lớn nhất trong các tung độ các đỉnh hình chữ
nhật đã cho. Khi đó hình H có toạ độ đỉnh dưới trái là (minx,miny) và đỉnh trên phải là
(max,maxy). Đó là phủ S cần tìm.

- Tính diện tích hình H là (maxx-minx)(maxy-miny)

- Tính diện tích s phủ bởi các hình chữ nhật (đã nêu rõ ở phương pháp chung)
- Phần diện tích cần tìm là: s1:=abs((maxx-minx)*(maxy-miny))-s

</div>
<span class='text_page_counter'>(18)</span><div class='page_container' data-page=18></div>
<span class='text_page_counter'>(19)</span><div class='page_container' data-page=19>

<b>Ví dụ 3. Diện tích phủ bởi các hình trịn</b>

Trên mặt phẳng cho N hình trịn. Tính diện tích phần mặt phẳng bị phủ bởi các hình
trịn trên.

<b>Dữ liệu:</b> Cho trong file INP.BL3 dịng đầu là số lượng hình tròn, từ dòng thứ 2 trở đi

mỗi dòng chứa 3 số nguyên dương là tọa độ x, y của tâm và bán kính của từng hình
trịn (các số trên cùng một dịng ghi cách nhau ít nhất 1 dấu cách)

<b>Kết quả:</b> Xuất ra màn hình

<b>- Ý tưởng:</b>

- Tìm hình chữ nhật nhỏ nhất có các cạnh song song với các trục toạ độ và chứa tồn
bộ N hình trịn

- Chia hình chữ nhật này thành lưới các ơ vng có cạnh 0.1 đơn vị, với mỗi ơ thuộc
hình chữ nhật kiểm tra xem ơ này có thuộc vào hình trịn nào đó hay khơng, nếu có
thì tăng diện tích cần tính lên 0.01 đơn vị.

- Chương trình

<b>Dạng 4. Xác định đa giác nhỏ nhất bao tất cả các</b>
<b>điểm, đa giác đã cho</b>

<b>Phương pháp:</b> Cho N điểm A1, A2, ..., AN trên mặt phẳng. Để xác định một đa giác

không tự cắt chứa một số điểm đã cho và bao tất cả các điểm còn lại ta làm như sau:
Bước 1. Tìm điểm có tung độ nhỏ nhất. Điểm đó sẽ là đỉnh đa giác

Bước 2. Giả sử ta đã chọn được điểm PM. Tìm điểm Pi sao cho góc hợp bởi PMPi và trục
hoành là nhỏ nhất và đồng thời góc này phải lớn hơn góc hợp bởi PMPM-1 và trục
hoành. Điểm Pi sẽ là một đỉnh của đa giác.

Bước 3. Lấy kết quả là dãy các đỉnh P tìm được.

Lưu ý: Với bài tốn tìm đa giác bao nhau thì cần ghi nhớ đa giác a bao đa giác b khi
mọi điểm trong đa giác b đều nằm trong đa giác a.

<b>Ví dụ 1. Đa giác khơng tự cắt</b>

Cho N điểm A1, A2, ..., AN trên mặt phẳng. Các điểm đều có toạ độ ngun và khơng
có 3 điểm bất kỳ trong chúng thẳng hàng. Hãy viết chương trình thực hiện các công
việc sau đây: Xác định một đa giác khơng tự cắt có đỉnh là một số điểm trong các
điểm đã cho và chứa tất cả các điểm cịn lại và có chu vi nhỏ nhất. Hãy tính diện tích
đa giác này.

<b>Dữ liệu:</b> cho trong tệp HCN.INP gồm n+1 dòng

</div>
<span class='text_page_counter'>(20)</span><div class='page_container' data-page=20>

+ Dòng i+1 (1≤ i ≤ N): Ghi 2 chữ số nguyên xi,yi là toạ độ đỉnh Ai.
Các số trên cùng một dòng cách nhau một khoảng trắng.

<b>Kết quả:</b> Xuất ra tệp HCN.Out

+ Dòng 1: Ghi 3 số K, V, S với K là số đỉnh đa giác tìm được, V là chu vi, S là diện tích
của nó.

+ Dịng i+1(1≤ i ≤ K): Ghi toạ độ của đỉnh đa giác.

<b>- Ý tưởng:</b>

- Tìm điểm có tung độ nhỏ nhất. Điểm đó sẽ là đỉnh đa giác

</div>
<span class='text_page_counter'>(21)</span><div class='page_container' data-page=21></div>
<span class='text_page_counter'>(22)</span><div class='page_container' data-page=22>

<b>Ví dụ 2. Đa giác bao nhau</b>

Cho N đa giác thoả mãn các tính chất

- Với 2 đa giác bất kỳ ln có một đa giác mà mọi điểm của nó nằm trong đa giác kia.
- Các cạnh của chúng khơng có điểm chung.

Bài tốn đặt ra là: Với mỗi đa giác i, có bao nhiêu đa giác bao nó? (i nằm trong bao

nhiêu đa giác)

<b>Dữ liệu vào:</b> Ghi trong tập tin văn bản Dagiac.Inp.

- Dòng đầu tiên ghi số tự nhiên N (3≤N≤10000).

- Trên N dịng tiếp theo: Dịng thứ i+1 ghi thơng tin về đa giác có số hiệu thứ i. Bao
gồm số đầu tiên Si là số đỉnh của đa giác (Si≥3), Si cặp số nguyên tiếp theo lần lượt là
hoành độ và tung độ các đỉnh của đa giác.

Các số trên cùng dịng cách nhau bởi ít nhất một
khoảng trắng.

<b>Dữ liệu ra:</b> Ghi trong tập tin Dagiac.Out
- Gồm N dòng

- Dòng thứ i: Ghi số lượng đa giác bao đa giác i.

<b>- Ý tưởng:</b>

- Sử dụng các mảng a,vt,kq (với a[i] lưu giá trị hoành độ nhỏ nhất của các đỉnh của
đa giác thứ i, vt[i] chỉ đa giác thứ i, mảng kq lưu kết quả)

- Thực hiện sắp xếp các đa giác theo thứ tự tăng dần của giá trị hoành độ nhỏ nhất
của các đỉnh của các đa giác.

- Do theo điều kiện bài toán là với 2 đa giác bất kỳ ln có một đa giác mà mọi điểm
của nó nằm trong đa giác kia nên KQ[vt[i]] =i-1

</div>
<span class='text_page_counter'>(23)</span><div class='page_container' data-page=23>

<b>Ví dụ 3. Hình chữ nhật bao nhau</b>

Cho N hình chữ nhật trên mặt phẳng mà các cạnh song song với các trục toạ độ. Biết
hình chữ nhật i bao hình chữ nhật j nếu cả 4 đỉnh của hình chữ nhật j đều nằm trong
hình chữ nhật i hoặc nằm trên cạnh của hình chữ nhật i.

Một dãy các hình chữ nhật được gọi là hình chữ nhật bao nhau chiều dài k (k≥1) nếu
dãy này gồm các hình chữ nhật H1, H2, ..., Hk sao cho hình chữ nhật i bao hình chữ
nhật i+1 với i=1 ... (k-1). Hãy tìm số k lớn nhất nói trên.

<b>Dữ liệu vào:</b> Được cho trong tập tin HCN.INP

</div>
<span class='text_page_counter'>(24)</span><div class='page_container' data-page=24>

- N dòng tiếp theo, dòng thứ i ghi 4 số nguyên x1, y1, x2, y2 (-10000<
x1,y1,x2,y2<10000) lần lượt là hoành độ, tung độ các đỉnh trái trên, phải dưới của
hình chữ nhật.

<b>Kết quả:</b> Được ghi vào tệp văn bản HCN.OUT gồm một dòng chứa số nguyên duy

nhất là số k tìm được hoặc số -1 nếu không tồn tại số k thoả điều kiện đề bài.

<b>- Ý tưởng:</b>

- Tính diện tích các hình chữ nhật (HCN)

- Sắp xếp lại các HCN theo thứ tự không giảm của diện tích các HCN
- Lập hàm kiểm tra HCN i bao HCN j, thoả mãn điều kiện:

(x1[i]<=x1[j]) and (y1[i]>=y1[j]) and (x2[i]>=x2[j]) and (y2[i]<=y2[j])

- Xác định số lượng các HCN bao HCN i và lưu vào phần tử mảng kq[i] biết rằng:
nếu thì kq[i]:=kq[j]+1

</div>
<span class='text_page_counter'>(25)</span><div class='page_container' data-page=25></div>
<span class='text_page_counter'>(26)</span><div class='page_container' data-page=26>

<b>Ví dụ 4. Hình chữ nhật bao nhau</b>

Hình chữ nhật A bao hình chữ nhật B nếu mọi điểm thuộc hình chữ nhật B đều nằm
trong hoặc thuộc hình chữ nhật A.

Trong mặt phẳng Oxy cho n hình chữ nhật có các cạch song song với các trục toạ độ.
Yêu cầu:

1. Tìm số hình chữ nhật bao nhau nhiều nhất (số lượng hình phải >1).

2. Trong số các tập hình chữ nhật bao nhau, tìm tập các hình chữ nhật bao nhau có
tổng diện các diện tích của các hình chữ nhật trong tập là lớn nhất.

3. Tìm hiệu diện tích của hình chữ nhật nhỏ nhất bao tất cả các hình chữ nhật đã cho
với diện tích của phần mặt phẳng bị phủ bởi các hình chữ nhật đã cho.

<b>Dữ liệu vào:</b> Cho trong tệp văn bản HCN.IN

- Dòng đầu: n (số lượng hình chữ nhật, 1≤N≤1000)

- n dịng tiếp theo: Mỗi dòng chứa 4 số dạng a, b, c, d (a, b, c, d là các số nguyên)
với (a, b) và (c, d) là toạ độ của hai đỉnh đối tâm của hình chữ nhật.

<b>Kết quả:</b> Xuất ra tệp văn bản HCN.Out

- Dịng đầu: Cho biết tập các hình chữ nhật bao nhau nhiều nhất theo dạng k l m n ...
với ý nghĩa-Hình chữ nhật thứ k thuộc hình chữ nhật thứ l, hình chữ nhật thứ l thuộc
hình chữ nhật thứ m, hình chữ nhật thứ m thuộc hình chữ nhật n ... nếu khơng có thì
ghi từ "khong"

- Dịng thứ 2: Cho biết tập các hình chữ nhật bao nhau có tổng các diện tích của các
hình chữ nhật trong tập hợp là lớn nhất theo qui cách như dịng thứ nhất. Nếu khơng
thì ghi số 0.

- Dòng thứ 3: Chứa con số biểu diễn hiệu diện tích hình chữ
nhật nhỏ nhất bao tất cả hình chữ nhật đã cho với diện tích
của phần mặt phẳng bị phủ bởi các hình chữ nhật đã cho.

<b>- Ý tưởng:</b>

- Lưu tọa độ các đỉnh hình chữ nhật vào 4 mảng x1,y1,x2,y2

- Dùng mảng bao(n,n) để đánh dấu các hình chữ nhật bao nhau: Với bao[i,j]=1 có
nghĩa hình chữ nhật i bao hình chữ nhật j, bao[i,j]=0 thì ngược lại.

- Dãy hình chữ nhật thứ i, k, j gọi là bao nhau nếu (Bao[i,k]+bao[k,j]>bao[i,j]) và
(bao[i,k]>0) và (bao[k,j]>0). Sử dụng mảng KQ để lưu các hình chữ nhật k thoả mãn
- Hình chữ nhật nhỏ nhất bao tất cả các hình chữ nhật đã cho là hình chữ nhật có toạ
độ góc dưới phải là (xmin,ymin) và toạ độ góc trên trái là (xmax,ymax)

</div>
<span class='text_page_counter'>(27)</span><div class='page_container' data-page=27></div>

<!--links-->