CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VỆT NAM

Độc lập - Tự do - Hạnh phúc
ĐƠN YÊU CẦU CÔNG NHẬN SÁNG KIẾN
Kính gửi: Trường THPT Chun Bình Long, Tỉnh Bình Phước
Chúng tơi ghi tên dưới đây:
Số

Họ và tên

TT

Ngày,

Nơi cơng tác

tháng, năm

Chức

Trình độ

Tỷ lệ (%)

danh

chun

đóng góp

sinh

01

Đỗ Thái Thanh

06/02/1981

02

Trần Thị Hịa

08/08/1989

03

Nguyễn Thị Văn

20/09/1993

mơn
THPT chuyên

Tổ

Thạc Sỹ

Bình Long
THPT chuyên

Trưởng


CNTT
Cử nhân

Bình Long
THPT chuyên
Bình Long

Giáo viên
Giáo viên

CNTT
Cử nhân
CNTT

40 %
30%
30%

Là đồng tác giả đề nghị xét công nhận sáng kiến: “Ứng Dụng Một Số Đối Tượng
Hình Học Phẳng Trong Dạy Học Sinh Giỏi Môn Tin Học”
Với những thông tin về sáng kiến cụ thể như sau:
1. Chủ đầu tư tạo ra sáng kiến: Trường THPT Chuyên Bình Long
2. Lĩnh vực áp dụng sáng kiến: Công nghệ thông tin
3. Ngày sáng kiến được áp dụng: Từ ngày 05 tháng 02 năm 2022
4. Mô tả bản chất sáng kiến:
4.1 Đối tượng đề nghị cơng nhận là sáng kiến (loại hình sáng kiến): Giải pháp
tác nghiệp
4.2 Mơ tả tính mới của sáng kiến:
- Trong toán học, khi giải quyết các bài tốn hình học chúng ta thường nhìn
trực quan để tư duy, nhưng trong Tin học thì khơng vậy. Các bài tốn về hình học có

thể rất đơn giản nhưng để lập trình cho máy tính hiểu và giải quyết được là cả vấn
đề khó, có một số cơng việc sẽ xuất hiện với các em học sinh học tin học, đầu tiên là
việc đưa được ra mơ hình tốn thứ đến nữa là phải chuyển đổi mơ hình tốn đó
thành chương trình. Có điều khó khăn là, khi giải các bài tốn về hình học việc so
sánh giá trị của hai đối tượng nào đó thường phải xử lý dưới dạng số nguyên (máy


2
tính khơng thể so sánh hai số thực), hơn nữa trong tin học việc giải các bài tốn
hình học lại thiên về việc xử lý trên rất nhiều đối tượng vì vậy cách thức tổ chức dữ
liệu, cách thức xây dựng cơng thức, phương pháp tính tốn là một vấn đề cần hệ
thống lại để xây dựng cho các em học sinh có cách nhìn tổng quan về vấn đề này.
- Các đề thi HSG Tin học thường có các bài tốn hình học u cầu tính tốn
rất kĩ với độ chính xác về kết quả cao, cần vận dụng nhiều kiến thức tổng hợp.
- Học sinh khi gặp các bài tốn về hình học sẽ rất sợ vì ngồi việc phải áp
dụng các mơ hình tốn học cịn phải sử dụng các cấu trúc dữ liệu phù hợp để giải
quyết.
- Tài liệu bồi dưỡng HSG Tin rất ít khơng như một số bộ môn khác, nhất là tài
liệu về chun đề Hình học và các bài tốn cụ thể cần giải quyết.
Qua quá trình tham gia giảng dạy và bồi dưỡng học sinh giỏi, chúng tôi nhận
thấy: nhiều bài tốn địi hỏi học sinh phải tìm ra mơ hình toán học cụ thể từ yêu cầu
phức tạp của bài tố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 toá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 toá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 tốn thường gặp trong q trình dạy chun Tin và Bồi dưỡng học sinh
giỏi dự thi các cấp. Chúng tôi mạnh dạn viết đề tài “Ứng Dụng Một Số Đối Tượng
Hình Học Phẳng Trong Dạy Học Sinh Giỏi Mơn Tin Học” nhằm để tổng hợp các

bài toán vận dụng đối tượng hình học mà Chúng tơi đã áp dụng trong q trình
giảng dạy.
4.3 Mơ tả các bước thực hiện sáng kiến:
Bước 1: Lý thuyết
Bước 2: Một số bài tập minh hoạ (có lời giải chi tiết)
Bước 3: Một số bài tập vận dụng (tự giải)
Chúng tơi xin trình bày chi tiết các bước thực hiện sáng kiến như sau:
I.
LÝ THUYẾT
a. Biểu diễn các đối tượng hình học cơ bản trong máy tính
Tác giả, đồng tác giả ký tên xác nhận:


3
Như chúng ta đã biết, các khái niệm: điểm, đoạn thẳng, đường thẳng là
những khái niệm cơ sở nhất trong hình học nói chung. Để biểu diễn các đối tượng
nói trên trong tin học ta thường sử dụng cách biểu diễn phổ biến như sau:
i.Điểm
Point=record
x,y:real;
end;
ii.Đường thẳng
Line=record
P1,P2:Point;
end;
iii.Đa giác
Polygon=Array[1..n] of Point;

Để thuận lợi thì khi biểu diễn đa giác ta nên thêm hai đỉnh ở đầu và cuối:
đỉnh 0 bằng đỉnh n và đỉnh n + 1 bằng đỉnh 1. Khi đó, biểu diễn đa giác lại

như sau:
Polygon=Array[0..n+1] of Point;
 Một số khái niệm:
 Đường gấp khúc
Một đường gấp khúc trên mặt phẳng gồm một dãy liên tiếp các đoạn thẳng
[P1,P2], [P2,P3],…, [Pk-1,Pk], mỗi đoạn thẳng được gọi là cạnh, các đầu mút của các
đoạn thẳng gọi là đỉnh.
 Đa giác
Một đa giác là một đường gấp khúc khép kín tức điểm Pk trùng với điểm P1.
 Đa giác tự cắt
Một đa giác được gọi là tự cắt nếu có hai cạnh khơng liên tiếp có điểm chung.
 Đa giác lồi
Một đa giác lồi được gọi là lồi nếu đa giác luôn nằm cùng một phía đối với
đường thẳng đi qua một cạnh bất kì của đa giác. Đa giác lồi là đa giác khơng tự cắt.
1

Trong các bài tốn hình học, phần lớn các đối tượng đều được thể hiện trên

hệ trục tọa độ Descartes, việc biểu diễn các thành phần tọa độ có thể sử dụng cả
kiểu số thực và kiểu số ngun của ngơn ngữ lập trình. Một số kiểu dữ liệu của
Pascal hay sử dụng.
2

+ Kiểu số nguyên:
Tác giả, đồng tác giả ký tên xác nhận:


4
Tên kiểu
Shortint

Byte
Integer
Word
LongInt
3
+ Kiểu số thực:
Tên kiểu
Single

Phạm vi
-128 → 127
0 → 255
-32768 → 32767
0 → 65535
-2147483648 → 2147483647

Dung lượng
1 byte
1 byte
2 byte
2 byte
4 byte

Phạm vi
1.5×10-45 → 3.4×10+38

Dung lượng
4 byte

Real


2.9×10-39 → 1.7×10+38

6 byte

Double

5.0×10-324 → 1.7×10+308

8 byte

Extended

3.4×10-4932 → 1.1×10+4932

10 byte

Một trong những khó khăn gặp phải khi giải quyết các bài tốn hình học
là ta phải làm việc với số thực. Khi làm việc với số thực bao giờ ta cũng phải
chấp nhận với những sai số nhất định. Vì vậy khi so sánh hai giá trị với nhau
ta chú ý không được dùng dấu “=”, mà phải xét trị tuyệt đối hiệu hai giá trị
với một giá trị Epsilon nào đó. Ở đây, Epsilon là một số tương đối bé, tuỳ vào
yêu cầu của bài tốn mà ta có chọn lựa về giá trị của nó.
Function Equal(x,y:real):Boolean;
Begin
Equal:= abs(x-y)<=Eps;
end;
b. Các phương pháp hình học
i.Khoảng cách giữa hai điểm
Cho 2 điểm A  x A ; y A  và B  xB ; y B  , khoảng cách giữa hai điểm A, B được

tính: AB 

 xA 

2

xB    y A  y B 

2

Function Dist(p1,p2:Point):Real;
Begin
Dist:=sqrt(sqr(p1.x-p2.x)+sqr(p1.y-p2.y));
end;
ii.Vị trí tương đối giữa 3 Điểm
Cho 3 điểm A  x A ; y A  , B  xB ; y B  và C  xC , yC  , Có 3 khả năng xảy ra:

Tác giả, đồng tác giả ký tên xác nhận:


5

Rẽ phải
k

xB  x A

Rẽ trái
xC  x B


y B  y A yC  y B

Đi thẳng

 x B  x A  yC  y B    y B  y A  xC  x B 

Nếu k = 0 thì 3 điểm A, B, C thẳng hàng
Nếu k < 0 thì rẽ phải
Nếu k > 0 thì rẽ trái

Hàm CCW sau trả ra -1 nếu là rẽ phải, 1 nếu rẽ trái, 0 nếu 3 điểm thẳng
hàng.
Function CCW(p1,p2,p3:Point):Integer;
Var
a1, b1, a2, b2, t: Real;
begin
a1 := p2.x – p1.x;
b1 := p2.y – p1.y;
a2 := p3.x – p2.x;
b2 := p3.y – p2.y;
t := a1*b2 – a2*b1;
if Abs(t) < Eps then CCW := 0
else
if t > 0 then CCW := 1
else CCW := -1;
end;
iii.Phương trình đường thẳng qua hai điểm
Phương trình đường thẳng qua 2 điểm A  x A ; y A  và B  xB ; y B  có dạng:

x  xA

y  yB

  x  x A  y B  y A    y  y B  x B  x A  0
xB  x A yB  y A
Để biểu diễn đường thẳng ta có thể biểu diễn bằng toạ độ hai điểm trên đường
thẳng đó. Nhưng đơi khi để tiện lợi cho tính tốn, ta phải có được phương
trình dưới dạng tổng qt của nó.
Procedure PointToLine(p1,p2:Point; Var a,b,c:Real);
Begin
a:=p2.y-p1.y;
b:=p1.x-p2.x;
Tác giả, đồng tác giả ký tên xác nhận:


6
c:=-(a*p1.x+b*p1.y);
end;
iv. Diện tích đa giác
Trong mặt phẳng với hệ tọa độ Đề-các vng góc, Cho đa giác P=P1P2...Pn
khơng tự cắt, trong đó điểm Pi có tọa độ (xi, yi). Bổ sung thêm điểm P0 trùng với Pn
và điểm Pn+1 trùng với P1, khi đó diện tích đa giác được tính:

S

1
2

n

x

i 1

i 1

 xi ( yi 1  yi )

Function Area(P:Polygon):Real;
Var i:longint; S:real;
begin
P[0]:=P[n];
P[n+1]:=P[1];
S:=0;
for i:=1 to n do
S:=S+(P[i+1].x-P[i].x)*(P[i+1].y+P[i].y);
Area:=abs(S)/2;
end;
Chú ý:
- Ta có thể xác định phép đánh số các đỉnh đa giác là thuận hay nghịch dựa vào
cơng thức tính diện tích đa giác: Bỏ dấu giá trị tuyệt đối trong công thức khi đó S>0
tương ứng với phép đánh số thuận và S<0 tương ứng với phép đánh số nghịch.
- Đường biên đa giác phải là một đường gấp khúc khép kín, khơng tự cắt. Cơng
thức tính diện tích trên sẽ sai nếu dữ liệu vào không thỏa mãn điều kiện này. Ví dụ
một đa giác gồm 4 đỉnh (0;0), (1;1), (0; 1) và (1;0), áp dụng cơng thức tính diện tích
trên cho đa giác này là 0, tuy nhiên trên thực tế thì diện tích miền này là 0.5.
v.Bao lồi
Trong hình học tính tốn, bao lồi (convex hull) của một tập điểm là tập lồi nhỏ
nhất (theo diện tích, thể tích, ...) mà tất cả các điểm đều nằm trong tập đó.

Tác giả, đồng tác giả ký tên xác nhận:



7

Một cách trực quan, nếu ta coi các điểm trong một tập hợp là các cái đinh đóng
trên một tấm gỗ, bao lồi của tập điểm đó có viền ngồi tạo bởi sợi dây chun mắc
vào các cái đinh sau khi bị kéo căng về các phía như hình vẽ sau:

Thuật tốn tìm bao lồi trên mặt phẳng
Bài tốn tìm bao lồi của một tập điểm trên mặt phẳng là một trong những bài
toán được nghiên cứu nhiều nhất trong hình học tính tốn và có rất nhiều thuật tốn
để giải bài toán này. Sau đây là hai thuật toán phổ biến nhất:
Thuật tốn bọc gói
Thuật tốn bọc gói (Gift wrapping algorithm) hay cịn gọi là thuật tốn Jarvis
march là một trong những thuật tốn tìm bao lồi đơn giản và dễ hiểu nhất. Tên thuật
toán xuất phát từ sự tương tự của thuật toán với việc đi bộ xung quanh các điểm và
cầm theo một dải băng gói quà.
- Bước đầu tiên của thuật toán là chọn một điểm chắc chắn nằm trong bao lồi, ví
dụ, điểm có tung độ lớn nhất (nếu có nhiều điểm cùng có tung độ lớn nhất thì có thể
chọn điểm tung độ lớn nhất và hoành độ lớn nhất).
- Xuất phát từ điểm này, mục tiêu của ta là sẽ lần lượt đi đến các điểm khác cho đến
khi quay trở lại điểm ta chọn lúc đầu.
- Ban đầu, ta nhìn về phía bên phải. Khi đi đến các điểm khác, ta sẽ lưu lại:
+ Điểm P mà ta đang chọn


+ Vector v chỉ hướng ta đang nhìn.
Tác giả, đồng tác giả ký tên xác nhận:


8

- Tiếp theo, thuật toán sẽ lặp lại liên tục các bước sau cho đến khi tìm được bao lồi.
+ Ta quay mặt theo chiều kim đồng hồ cho đến khi ta nhìn thấy một điểm, gọi
điểm đó là Q.
+ Rồi ta cầm theo dải băng và đi đến điểm Q. Khi ta đến điểm đấy, ta thay:




o v thành PQ
o P thành Q
- Thuật toán kết thúc, khi ta quay trở về điểm ban đầu. Lúc này ta đã đi đến tất
cả các đỉnh của bao lồi theo chiều kim đồng hồ.
Để xác định điểm ta nhìn thấy đầu tiên khi ta quay mặt theo chiều kim đồng
hồ, ta duyệt tất cả các điểm R trong tập, ngoại trừ điểm P. Với mỗi điểm, ta xét








vector u = PR , u tạo với v một góc θ nhỏ nhất sẽ tương ứng với điểm. Để tìm
 

u .v
cos    
θ nhỏ nhất, ta tìm cosθ lớn nhất, với
u .v


Với mỗi lần tìm điểm tiếp theo, ta cần duyệt qua tất cả các điểm trong tập, vì
vậy độ phức tạp của mỗi lần tìm điểm là O(n) với n là số lượng điểm trong tập. Số
lần tìm điểm tiếp theo phụ thuộc vào số lượng điểm là đỉnh của bao lồi, gọi số
lượng điểm đó là h, khi đó độ phức tạp của cả thuật tốn là O(nh). Trong trường
hợp xấu nhất, h=n hay tất cả các điểm trong dữ liệu vào tạo thành một đa giác lồi,
độ phức tạp của thuật tốn là O(n2), khơng đủ nhanh khi n>5000.
Thuật tốn Graham
Thuật tốn Graham có độ phức tạp trong trường hợp xấu nhất nhỏ hơn thuật
tốn bọc gói, song thuật toán Graham lại phức tạp hơn.
- Đầu tiên, ta xác định một điểm mà chắc chắn thuộc bao lồi. Thơng thường, khi cài
đặt người ta chọn điểm có tung độ nhỏ nhất (nếu có nhiều điểm như vậy thì chọn
điểm trái nhất). Gọi điểm này là điểm O.
- Chọn hệ trục tọa độ có gốc là điểm vừa chọn, đổi các tọa độ các điểm còn lại theo
hệ trục tọa độ mới (chú ý lúc cài đặt thường ta khơng đổi trục tọa độ, nhưng khi tính
góc hoặc sắp xếp ở bước tiếp theo cần chú ý tránh nhầm lẫn).

Tác giả, đồng tác giả ký tên xác nhận:


9
- Tiếp theo, ta sắp xếp các điểm còn lại theo thứ tự tăng dần của góc tạo bởi trục


hồnh theo chiều dương và OI với I là một trong các điểm còn lại.
- Ta xét các điểm theo thứ tự ta vừa sắp xếp, với mỗi điểm ta sửa lại bao lồi H. Gọi
điểm đầu tiên được cho vào bao lồi H là H1, điểm cuối cùng là Hh (ban đầu h=0).
Khi xét mỗi điểm ta làm như sau:

1. Thêm điểm P vào cuối bao lồi H. Tức là ta tăng h lên 1 và đặt Hh=P.
2. Nếu h<3, xét tiếp điểm tiếp theo, ngược lại làm bước 3.

3. Xét 3 điểm Hh,Hh−1 và Hh−2. Có thể sau khi cho thêm điểm Hh, ta biết được




điểm Hh−1 chắc chắn không nằm trong bao. Gọi u H h  2 H h  1 và v H h  1 H h .




Nếu khi đi theo hướng u rồi đi theo hướng v là ta đã bẻ góc ngược chiều
kim đồng hồ, hay u  v > 0, thì cả ba điểm đều tạm thuộc bao, và ta xét tiếp






điểm tiếp theo. Nhưng nếu u  v < 0, thì góc H h  2 H h  1 H h sẽ tạo ra đa giác




lõm và điểm Hh−1 phải bị loại bỏ, có nghĩa là Hh−1 được đặt là Hh và h giảm đi
1. Sau đó quay lại bước 2 cho đến khi xét hết các điểm.
Ví dụ:

- Ta đang xây dựng bao lồi, đến vị trí h=4
Tác giả, đồng tác giả ký tên xác nhận:



10


- Góc H h  2 H h  1 H h lõm, nên ta cần bỏ điểm H3 khỏi bao lồi
Sau q trình trên, ta đã có một bao lồi H1,H2,...,Hh sắp xếp ngược chiều kim
đồng hồ.
Để đảm bảo ta loại bỏ điểm và thêm điểm với độ phức tạp O(1), ta có thể dùng
cấu trúc dữ liệu stack.
Về độ phức tạp của thuật toán, ta thấy bước sắp xếp các điểm có độ phức
tạp O(nlogn). Mỗi điểm được cho vào bao nhiều nhất một lần nên tổng độ phức tạp
của các bước thêm điểm là O(n), và mỗi điểm bị loại ra khỏi bao nhiều nhất một lần
nên tổng độ phức tạp của các bước xóa điểm là O(n), do đó độ phức tạp của bước
xét các điểm là O(n). Vậy, độ phức tạp của thuật toán Graham là O(nlogn), phù hợp
cho hầu hết các bài toán.
Cài đặt:

Function CCW(P1,P2,P3:Point):Integer;
Var k:real;
Begin
k:=(P2.x-P1.x)*(P3.y-P2.y)-(P3.x-P2.x)*(P2.y-P1.y);
if abs(k)<=Eps then CCW:=0
else
If k>0 then CCW:=1
else CCW:=-1;
End;
Procedure Doicho(Var p1,p2:Point);
var Tg:Point;
begin
tg:=p1;

p1:=p2;
p2:=tg;
end;
Function Check(p1,p2:Point):Boolean;
var c:integer;
begin
c:=CCW(a[1],p1,p2);
Check:=false;
if c>0 then Check:=true
else
if (c=0) and ((p1.x(p1.ythen Check:=true;
end;
Tác giả, đồng tác giả ký tên xác nhận:


11
Procedure QuickSort(L,R:longint);
var x:Point; i,j:longint;
begin
i:=L;
j:=R;
x:=a[(i+j) div 2];
repeat
while Check(a[i],x) do inc(i);
While Check(x,a[j]) do dec(j);
if i<=j then
begin
Doicho(a[i],a[j]);

inc(i);
dec(j);
end;
until i>j;
if iif Lend;
Procedure graham;
var i,k:longint;
begin
// Tim diem co tung do nho nhat,
// neu co nhieu tung do nho nhat, chon diem co
hoanh do nho nhat
k:=1;
for i:=2 to n do
if (a[i].y(a[i].xDoicho(a[1],a[k]);
Quicksort(2,n);
a[n+1]:=a[1];
a[0]:=a[n];
b[1]:=a[1];
b[2]:=a[2];
m:=2;
for i:=3 to n+1 do
begin
while (m>=2) and (CCW(b[m-1],b[m],a[i])<=0)
do dec(m);
inc(m);
b[m]:=a[i];

end;
dec(m);
end;
II.
MỘT SỐ BÀI TẬP MINH HỌA
Bài 1. Đếm hình vng
Tác giả, đồng tác giả ký tên xác nhận:


12
Trong mặt phẳng tọa độ, cho một lưới các điểm ngun có kích thước n+1
dịng và m+1 cột. Điều đó có nghĩa là nếu (x, y) là một điểm nguyên trong lưới thì
0 ≤ x ≤ m và 0 ≤ y ≤ n. Người ta có thể chọn 4 điểm nào đó trong lưới để tạo thành
các hình vng như hình bên dưới (n=5 và m=8).

Trong số các hình vng này, diện tích của một số hình vng là lẻ (diện tích
của B là 17), hình vng cịn lại có diện tích là chẵn (diện tích của A là 4). Hãy đếm
xem tổng cộng có bao nhiêu hình vng có diện tích lẻ.
Input: Cho bởi file văn bản HVUONG.INP
- Là hai số nguyên n và m cách nhau một khoảng trắng (1 ≤ n, m ≤ 105)
Output: Ghi vào tập văn bản HVUONG.OUT
- Là số lượng số hình vng có diện tích lẻ. Kết quả đảm bảo số lượng này là số
ngun 64 bít.
Ví dụ:
HVUONG.INP
12
33
Hướng dẫn thuật tốn:

HVUONG.OUT

2
12

- Hình vng được xét phải có cạnh là một số lẻ.
- Một hình vng có độ dài với L điểm ở trên một cạnh và các cạnh song song với
trục tọa độ, gọi độ dài đó là i có thể được di chuyển theo (n-i+1)  (m-i+1) vị trí
khác nhau trên lưới. (i = L-1)
- Chúng ta xét trường hợp số hình vng có các cạnh song song với các đường chéo
trên lưới vng có L điểm. Dễ dàng thấy được nếu lưới vng có

điểm mỗi cạnh

thì sẽ có L-2 hình vng (Hay nói cách khác có i -1 hình vng) có cạnh song song
với các đường chéo. Minh họa bằng hình vẽ sau:

Tác giả, đồng tác giả ký tên xác nhận:


13

Có 3 hình vng có các cạnh song song với các đường chéo trên lưới vng có 5
điểm với độ dài 4.
Từ đó ta có cơng thức tổng qt cho trường hợp NM như sau:

min( n ,m )

(( n  i  1 ) ( m  i  1 )  ( i  1 ) ( n  i  1 ) ( m  i  1 ))

i1
min( n ,m )


( i ( n  i  1 ) ( m  i  1 )) Với i lẻ

i1

Độ phức tạp thuật toán: O(min(n,m))

Code tham khảo:
uses math;
const fi='HVUONG.INP'; fo='HVUONG.OUT';
var n,m:longint;
f:text;
res:int64;
procedure doc;
begin
assign(f,fi); reset(f);
readln(f,n,m);
close(f);
end;
procedure xuly;
var i:longint;
begin
res:=0;
for i:=1 to min(n,m) do
if odd(i) then
res:=res+int64(i)*(m-i+1)*(n-i+1);
end;
procedure ghi;
begin
assign(f,fo); rewrite(f);

writeln(f,res);
Tác giả, đồng tác giả ký tên xác nhận:


14
close(f);
end;
begin

end.

doc;
xuly;
ghi;

Bài 2. Lục giác đều (OLP 2008)
Lục giác đều là một dạng cấu trúc đặc biệt trong thiên nhiên. Bạn có thể gặp lục
giác đều khi quan sát cách bố trí cánh của nhiều loại hoa, khi quan sát cấu trúc của
tổ ong, khi nghiên cứu sơ đồ liên kết giữa Các bon và Ôxy trong các hợp chất hữu
cơ và vô cơ. Mũ đinh ốc cũng tạo thành một lục giác đều. Lục giác đều là một trong
số hiếm hoi các loại đa giác đều có thể phủ kín mặt phẳng.

Một bạn sinh viên quyết định chọn “Vai trò và vị trí của lục giác đều trong
thiên nhiên” làm đề tài báo cáo trong một buổi sinh hoạt ngoại khóa. Để chuẩn bị số
liệu cho bản thuyết trình của mình bạn đó đã khảo sát rất nhiều dữ liệu về cấu trúc
lục giác gặp trong thiên nhiên và cuộc sống. Mỗi dữ liệu khảo sát là một dãy tọa độ
6 đỉnh trong mặt phẳng của lục giác. Bạn sinh viên muốn biết 6 điểm này có thể là
đỉnh của một lục giác đều hay khơng. Ví dụ, nếu tọa độ của 6 điểm nhận được là (3,1), (6,6.19615), (0,6.19615), (9,1), (0, -4.19615), (6, -4.19615) thì câu trả lời là
có. Với dữ liệu phong phú thu thập được, việc kiểm tra trở thành một công việc
nặng nề và tẻ nhạt nếu khơng sử dụng máy tính.

u cầu: Cho tọa độ 06 đỉnh (xi, yi). Hãy kiểm tra xem 06 đỉnh trên có tạo thành
một hình lục giác đều hay khơng.
Input: Cho bởi file văn bản LUCGIAC.INP
Tác giả, đồng tác giả ký tên xác nhận:


15
- Là 06 cặp số thực (xi, yi), mỗi số cách nhau một khoảng trắng (-103 ≤ xi, yi ≤ 103).
Output: Ghi vào file văn bản LUCGIAC.OUT
- Nếu 06 đỉnh trên tạo thành hình lục giác đều, in ra YES.
- Nếu không, in ra NO.
Lưu ý: Các giá trị thực được so sánh với độ chính xác 10-4.
Ví dụ:

LUCGIAC.INP
-3 1 6 6.19615 0 6.19615 9 1 0 -4.19615 6 -4.19615
0 6 0 -4 6 6 6 -4 -1 1 9 1

LUCGIAC.OUT
YES
NO

Hướng dẫn thuật tốn
- Với mỗi đỉnh p[i], tính khoảng cách từ nó đến các đỉnh cịn lại lưu vào mảng kc.
Chú ý: khoảng cách (p[i], p[j]) = khoảng cách (p[j], p[i]) được tính là một.
- Sắp xếp mảng kc theo chiều tăng dần.
- Điều kiện để 6 đỉnh tạo thành lục giác đều là: (kc[1]=kc[6]) và (kc[7]=kc[12)
và (kc[13]=kc[15]).
- Chú ý : Khi so sánh hai số thực x, y có bằng nhau hay khơng ta sử dụng
abs(x-y)<=Eps, với Eps chọn một số thực nhỏ nào đó.

Độ phức tạp thuật toán: O(n2), với n = 15.

Code tham khảo
const fi='lucgiac.inp'; fo='lucgiac.out';
Eps=0.0001;
type toado=record
x,y:extended;
end;
var p:array[1..6] of toado;
kc:array[1..30] of extended;
N:longint;
f:text;
Procedure doc;
var i:longint;
begin
assign(f,fi); reset(f);
for i:=1 to 6 do
read(f,p[i].x,p[i].y);
close(f);
end;
Procedure khoangcach;
var i,j:longint;
Tác giả, đồng tác giả ký tên xác nhận:


16
begin
n:=0;
for i:=1 to 5 do
for j:=i+1 to 6 do

begin
inc(n);
kc[n]:=sqrt(sqr(p[i].x-p[j].x)+ sqr(p[i].yp[j].y));
end;
end;
Procedure xuli;
var i,j:longint;tmp:extended;
begin
for i:=1 to n-1 do
for j:=i+1 to n do
if kc[i]>kc[j] then
begin
tmp:=kc[i];
kc[i]:=kc[j];
kc[j]:=tmp;
end;
assign(f,fo); rewrite(f);
if
(abs(kc[1]-kc[6])and
(abs(kc[7]kc[12])write(f,'YES') else write(f,'NO');
close(f);
end;
begin
doc;
khoangcach;
xuli
end.
Bài 3. Đường đi nào

Đất nước X đang gặp nguy hiểm, có một con quỷ từ đâu tới phá rối người dân
nơi đây. Vốn là một đất nước có tinh thần yêu nước, không phải chờ đợi lâu, một
dũng sĩ đã ngay lập tức xách gươm lên và đi đánh quỷ. Dũng sĩ cần đi từ điểm A
thẳng tới điểm B rồi tới điểm C (Nơi con quỷ đang phá rối). Nhưng không may, khi
đến điểm B, dũng sĩ quên mất đi tới C bằng con đường nào bởi ở B có 3 sự lựa chọn
một là rẽ vng góc sang trái hoặc rẽ vng góc sang phải hoặc đi thằng để tới C.
Đúng lúc đó có một con đại bàng bay ngang qua và thấy rõ được con quỷ ở hướng
nào. Giả sử nếu bạn là con đại bàng và được cho biết trước tọa độ 3 điểm A, B, C,
hãy nói cho dũng sĩ nên rẽ trái, phải, hay đi thẳng nhé.
Tác giả, đồng tác giả ký tên xác nhận:


17
Input
Dòng 1, 2, 3 lần lượt chứa tọa độ 3 điểm A, B, C.
Mỗi dòng gồm 2 số nguyên là tọa độ tương ứng. ( |x|, |y| <= 109 )
Dòng 1, 2, 3 lần lượt chứa tọa độ 3 điểm A, B, C.
Mỗi dòng gồm 2 số nguyên là tọa độ tương ứng. ( |x|, |y| <= 109 )
Output
Gồm một dòng duy nhất. In ra “RIGHT” nếu dũng sĩ nên rẽ phải, “LEFT” nếu
rẽ trái và “TOWARDS” nếu đi thẳng.
Ví dụ:

Input
00

Output
RIGHT

01

11

-1 -1

TOWARDS

-3 -3
-4 -4

-4 -6

LEFT

-3 -7
-2 -6
Hướng dẫn thuật toán
Sử dụng hàm CCW để kiểm tra vị trí tương đối giữa 3 đỉnh. Độ phức tạp O(1)
Code tham khảo

const fi='P141SUMA.inp'; fo='P141SUMA.out';
Eps=1e-6;
type Point = record
x,y:longint;
end;
Tác giả, đồng tác giả ký tên xác nhận:


18
var A,B,C:Point;
f:text;

procedure doc;
begin
assign(f,fi); reset(f);
readln(f,A.x,A.y);
readln(f, B.x, B.y);
readln(f, C.x,C.y);
close(f);
end;
Function CCW(P1,P2,P3:Point):Integer;
Var k:real;
Begin
k:=(P2.x-P1.x)*(P3.y-P2.y)-(P3.x-P2.x)*(P2.y-P1.y);
if abs(k)<=Eps then CCW:=0
else
If k>0 then CCW:=1
else CCW:=-1;
End;
Procedure ghi;
begin
assign(f,fo); rewrite(f);
if CCW(A,B,C)>0 then writeln(f,'LEFT')
else
if CCW(A,B,C)=0 then writeln(f,'TOWARDS')
else writeln(f,'RIGHT');
close(f);
end;
Begin
doc;
ghi;
end.

Bài 4. Rào cây
Người ta muốn rào các cây ở một khu vờn để bảo vệ. Hàng rào được tạo bởi
một đường gấp khúc khép kín có có đỉnh là một số cây làm cột mốc, sao cho các
cây khác phải nằm trong hàng rào (một số cây có thể nằm trên biên)
Hãy xác định một phương án rào cây sao cho số cây phải làm cột mốc là ít nhất.
Input: Cho bởi file văn bản RAOCAY.INP
Dòng đầu số n≤10000 là số cây, các dòng tiếp, mỗi dịng là một cặp số ngun (ghi
cách nhau ít nhất một khoảng trắng) mơ tả hồnh độ và tung độ của một cây. Các
cây được đánh số từ 1 theo trình tự xuất hiện trong file.
Tác giả, đồng tác giả ký tên xác nhận:


19
Output: ghi ra file văn bản RAOCAY.OUT
Dòng đầu là số cây làm cột mốc, dòng sau là số hiệu các cây này theo đúng thứ tự
tạo hàng rào (ghi cách nhau ít nhất một dấu trắng)

Ví dụ: Hình vẽ trên mô tả một khu vườn
gồm 9 cây, hàng rào đi qua 4 cây làm cột
mốc (màu xám) có số hiệu (theo thứ tự)
7, 3, 1, 4 tương ứng với các file vào, ra
dưới đây:

RAOCAY.INP
9
04
-1 -1
40
-2 2
22

-1 1
0 -4
11
2 -1

RAOCAY.OUT
4
7314

Hướng dẫn thuật tốn
- Sử dụng thuật tốn Graham để tìm bao lồi trong một tập đỉnh cho trước. Độ phức
tạp thuật toán O(nlogn)

Code tham khảo
Const fi='RAOCAY.inp'; fo='RAOCAY.out';
maxn=10000; Eps=0.0000001;
type
Point=record
x,y,id:longint;
end;
Polygon=Array[0..maxn+1] of Point;
Var a,b:Polygon;
n,m:longint;
f:text;
Procedure Doc;
Tác giả, đồng tác giả ký tên xác nhận:


20
var i:longint;

begin
assign(f,fi); reset(f);
readln(f,n);
for i:=1 to n do
begin
readln(f,a[i].x,a[i].y);
a[i].id:=i;
end;
close(f);
end;
Function Equal(x,y:real):Boolean;
Begin
Equal:= abs(x-y)<=Eps;
end;
Function Dist(P1,P2:Point):Real;
Begin
Dist:=sqrt(sqr(P2.x-P1.x)+sqr(P2.y-P1.y));
end;
Function CCW(P1,P2,P3:Point):Integer;
Var k:real;
Begin
k:=(P2.x-P1.x)*(P3.y-P2.y)-(P3.x-P2.x)*(P2.y-P1.y);
if abs(k)<=Eps then CCW:=0
else
If k>0 then CCW:=1
else CCW:=-1;
End;
Procedure Doicho(Var p1,p2:Point);
var Tg:Point;
begin

tg:=p1;
p1:=p2;
p2:=tg;
end;
Function Check(p1,p2:Point):Boolean;
var c:integer;
begin
c:=CCW(a[1],p1,p2);
Check:=false;
if c>0 then Check:=true
else
if (c=0) and ((p1.x(p1.ythen Check:=true;
end;
Procedure QuickSort(L,R:longint);
var x:Point; i,j:longint;
Tác giả, đồng tác giả ký tên xác nhận:


21
begin

end;

i:=L;
j:=R;
x:=a[(i+j) div 2];
repeat
while Check(a[i],x) do inc(i);

While Check(x,a[j]) do dec(j);
if i<=j then
begin
Doicho(a[i],a[j]);
inc(i);
dec(j);
end;
until i>j;
if iif L
Procedure graham;
var i,k:longint;
begin
// Tim diem co tung do nho nhat,
// neu co nhieu tung do nho nhat, chon diem co
hoanh do nho nhat
k:=1;
for i:=2 to n do
if (a[i].y(a[i].xDoicho(a[1],a[k]);
Quicksort(2,n);
a[n+1]:=a[1];
a[0]:=a[n];
b[1]:=a[1];
b[2]:=a[2];
m:=2;
for i:=3 to n+1 do
begin

while (m>=2) and (CCW(b[m-1],b[m],a[i])<=0)
do dec(m);
inc(m);
b[m]:=a[i];
end;
dec(m);
end;
Procedure Ghi;
var i:longint;
begin
assign(f,fo); rewrite(f);
Tác giả, đồng tác giả ký tên xác nhận:


22
writeln(f,m);
// for i:=1 to m do writeln(f,b[i].x,' ',b[i].y);
for i:=1 to m do write(f,b[i].id,' ');
close(f);
end;
begin

end.

doc;
graham;
ghi;

III.
MỘT SỐ BÀI TẬP VẬN DỤNG

Bài 1. Chia đất
Có một mảnh đất, trên biên của nó có cắm một số cột mốc để mảnh đất có thể
xem như một đa giác có biên gồm các đoạn thẳng kề nhau nối các mốc này. Bắt đầu
từ một cột mốc nào đó được đánh số 1, người ta đi vòng quanh mảnh đất theo một
chiều xác định để đánh số các cột mốc kế tiếp (2, 3, ..., N) theo thứ tự
được gặp.
Yêu cầu: Hãy phân chia mảnh đất thành hai phần bằng một đoạn thẳng nối hai cột
nào đó để độ chênh lệch diện tích của hai phần được chia là nhỏ nhất. Đoạn thẳng
chia không được phần nào nằm ngồi mảnh đất và khơng được chứa cột mốc nào
ngồi hai cột mốc đầu mút của nó.
Input: Cho bởi file văn bản CHIADAT.INP
- Dòng đầu là số N (4N1000);
- N dòng tiếp theo, mỗi dòng ghi hai số nguyên x, y là các cặp toạ độ một cột mốc
(theo thứ tự các cột từ 1 đến N). Các số trên một dịng được ghi cách nhau ít nhất
một dấu cách.
Output: Ghi ra file văn bản CHIADAT.OUT
Ghi hai số ghi cách nhau ít nhất một dấu cách, là số hiệu của hai cột mốc tạo thành
đoạn thẳng chia.

Ví dụ:
CHIADAT.INP
10
21
22
00

4
CHIADAT.OUT
48

2

5

3
6

Tác giả, đồng tác giả ký tên xác nhận:

1
10

9
7

8


23
-2 2
-3 2
-2 -2
-1 -3
0 -3
0 -2
1 -2
Bài 2. Chia đa giác
Đức vua vương quốc XYZ tổ chức kén rể cho cơ cơng chúa duy nhất của
mình. Vì vậy, ơng đặt ra những yêu cầu rất cao cho con rể tương lai. Để có thể trở
thành con rể của ngài, các chàng trai thi nhau thể hiện mình. Sau khi vượt qua

những phần thi đòi hỏi sức khoẻ, lòng dũng cảm, … họ sẽ gặp phải một thử thách
vô cùng khó khăn, đó là phần thi về sự nhanh nhạy và thông minh. Đức vua sẽ cho
mỗi người một miếng bìa hình đa giác lồi N đỉnh. Đức vua yêu cầu các chàng trai
vẽ N-3 đường chéo bất kì sao cho 2 đường chéo bất kì khơng có điểm chung khác
các đầu mút. Với cách vẽ như vậy, chúng ta sẽ thu được N-2 hình tam giác. Đức vua
yêu cầu họ hãy tìm 2 cách chia:
 Một cách chia sao cho tam giác có diện tích lớn nhất trong N-2 tam giác là
lớn nhất.
 Một cách chia sao cho tam giác có diện tích lớn nhất trong N-2 tam giác là
nhỏ nhất.
Sau khi nhà vua đưa ra hình dạng của đa giác lồi, họ sẽ chỉ có 1 giây để đưa ra đáp
án của mình. Người đưa ra đáp án đúng nhất và nhanh nhất sẽ được chọn làm phò
mã. Bạn cũng là một người đã lọt vào vòng thi này. Hãy chứng tỏ khả năng của
mình đi!
Dữ liệu
 Dịng đầu tiên ghi số nguyên N là số đỉnh của đa giác.
 Trong n dòng sau, mỗi dòng ghi một cặp số nguyên là tọa độ các đỉnh của đa
giác. Các đỉnh được liệt kê theo chiều kim đồng hồ.
Kết qủa
 Dịng thứ nhất ghi diện tích của tam giác lớn nhất trong trường hợp 1.
 Dòng thứ hai ghi diện tích của tam giác lớn nhất trong trường hợp 2.
Các giá trị diện tích có độ chính xác 1 chữ số thập phân.
Giới hạn
 4 ≤ N ≤ 200.
6
 Các tọa độ là các số nguyên có trị tuyệt đối không quá 10 .
Input
Output
5
4.0

00
2.0
02
Tác giả, đồng tác giả ký tên xác nhận:


24
14
22
20
Bài 3. Vườn cây
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 chúng tơi sẽ
lấy đi, chú ý rằng, sau khi chúng tơi lấy câ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ó cùng bán kính r, cây thứ i có tọa độ tâm (xi, yi).
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).

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 tương ứng với bộ dữ liệu trong file dữ
liệu vào.
Subtask 1 (15/70 điểm): Giả thiết là n ≤ 2.
Subtask 2 (15/70 điểm): Giả thiết là n ≤ 3.
Subtask 3 (20/70 điểm): Giả thiết là n ≤ 4.
Subtask 4 (20/70 điểm): Giả thiết là n ≤ 10.
Ví dụ:

Input
1
20 4 1
11
51
71
20 20

Output
3

Bài 4. Bé và hình vng
Tác giả, đồng tác giả ký tên xác nhận:


25
Bé mới bắt đầu học mơn hình học tại trường mẫu giáo. Bé được học rất nhiều
điều thú vị như hình vng có 4 cạnh bằng nhau, cách lấy điểm đối xứng qua 1

điểm. Trước khi được nghỉ hè, cô giáo giao cho bé một bài toán và sau hè bé phải
nộp lại kết quả cho cơ giáo.
“Cho một hình vuông, 4 đỉnh theo thứ tự là A, B, C, D có tọa độ ngun. Chọn một
điểm X1 nằm ngồi hình vng đó, và điểm X2 đối xứng với X1 qua A, X3 đối xững
X2 qua B, X4đối xứng X3 qua C, X5 đối xứng X4 qua D.
Nhiệm vụ của bé là đếm số cách chọn điểm X1 có tọa độ nguyên thỏa mãn:


Qua các bước lấy đối xứng trên ta có X1 trùng với X5



Tứ giác X1X2X3X4 (theo đúng thứ tự X1, X2, X3, X4) là tứ giác lồi

Nhưng mà bé đã đi du lịch khắp đất nước Việt Nam xinh đẹp cùng bố mẹ trong mùa
hè, do đó bé quên bẵng mất bài tập hè cô giáo giao cho. Đến khi nhớ đến thì đã q
muộn để hồn thành (do bé không biết code). Các bạn hãy giúp đỡ bé để bé có được
phiếu bé ngoan nhé.
Input: Gồm 8 số nguyên lần lượt lượt là tọa độ các điểm A, B, C, D
Output : Một số nguyên duy nhất là số cách chọn điểm X1
Giới hạn
Subtask 1 (30%): Giá trị tuyệt đối tọa độ các đỉnh ≤ 1000
Subtask 2 (30%): Giá trị tuyệt đối tọa độ các đỉnh ≤ 100,000
Subtask 3 (40%): Giá trị tuyệt đối tọa độ các đỉnh ≤ 1000,000,000

Ví dụ:
Input
00022220

Output

1

Bài 5. Trụ sở xa nhất
Microhoo và Googloo là hai công ty Tin học cạnh tranh nhau ở cùng một
thành phố. Mỗi cơng ty có một số văn phòng nằm ở một số điểm trong thành phố.
Để bảo vệ thông tin quan trọng khỏi lọt đến đối thủ, cả hai công ty đã cam kết sẽ đặt
trụ sở chính càng xa nhau càng tốt. Cho trước vị trí của các văn phịng của
Microhoo và Googloo, nhiệm vụ của bạn là viết một chương trình để giúp hai cơng
ty chọn từ các văn phịng đã có để đặt trụ sở chính sao cho khoảng cách giữa hai trụ
sở chính của hai cơng ty là lớn nhất.
Dữ liệu vào
Tác giả, đồng tác giả ký tên xác nhận: