Trước tiên, chúng ta cùng xét bài toán:

Bài toán 1. Cho 4 điểm trên mặt phẳng. Hãy kiểm tra xem bốn điểm này có phải là đỉnh của một hình vuông có các cạnh song song với trục toạ độ hay không.

Nhận xét 1a. Hình vuông là hình chữ nhật có 4 cạnh bằng nhau.

Nhận xét 1b. Nếu x_A= x_B, x_C = x_D, y_A = y_D và y_B = y_C thì ABCD là hình chữ nhật (có các cạnh song song với trục toạ độ)

Bước 1. Bạn sắp xếp toạ độ 4 điểm theo thứ tự tăng dần theo hoành độ (trong hình, thứ tự các điểm sau khi sắp xếp là A, B, D, C). Sau đó chúng ta kiểm tra nhận xét 1b. Nếu đúng chúng ta qua bước 2, nếu sai ta ghi kết quả ‘SAI’.

Bước 2. Tính độ dài AB, BD, CD, DA. Nếu AB = BC = CD = DA thì ta ghi ‘DUNG’, nếu sai ta ghi ‘SAI’.

Như vậy chúng ta đã giải quyết xong bài toán 1. Tuy nhiên, nếu các cạnh hình vuông không song song với trục toạ độ thì bài toán 1 sẽ trở thành bài toán như sau:

Bài toán 2. Cho 4 điểm trên mặt phẳng. Hãy kiểm tra xem bốn điểm này có thể là đỉnh của 1 hình vuông hay không?

Input: File KTHV.INP gồm 4 dòng là toạ độ 4 điểm ban đầu.

Output: File KTHV.OUT chứa số 1 (hoặc -1) nếu 4 điểm đó có thể (không thể) là 4 đỉnh một hình vuông.

Ví dụ:

Nếu giải theo cách thông thường, ta không những kiểm tra độ dài 4 cạnh mà phải kiểm tra đến cả độ lớn 4 góc. Tôi đã nghĩ ra một giải thuật đơn giản hơn như sau :

Chúng ta cũng sắp xếp 4 điểm ban đầu theo thứ tự tăng dần theo hoành độ, ta được 4 điểm đã sắp xếp theo thứ tự là A, B, D, C. Sau đó, chúng ta sẽ tạo ra 4 điểm mới là A’, B’, C’, D’ sao cho x_A’ = x_B’= min (các hoành độ của A, B, C, D) ; x_C’ = x_D’ = max (các hoành độ của A, B, C, D); y_A’ = y_D’ = min (các tung độ của A, B, C, D); y_B’ = y_C’ = max (các tung độ của A, B, C, D).

Bây giờ chúng ta kiểm tra giá trị k = (A’B’ = B’C’ = C’D’ = D’A’) and (AB = BC = CD = DA). Nếu k = Truethì ABCD là hình vuông, ngược lại thì ABCD không phải là hình vuông.

Sau đây là chương trình của bài 2.

Program KiemTraHinhVuong;

Const fi = 'KTHV.INP';

fo = 'KTHV.OUT';

Type Point = Record

x,y:real;

End;

Var P : Array[1..8] of Point; {Các điểm A,B,D,C,A’,B’,C’,D’}

A : Array[1..8] of Real; {AB,BC,CD,DA,A’B’,B’C’,C’D’,D’A’}

i,j : byte;

f:text;

FunctionD(A,B:Point):real;

Begin

D:=sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));

End;

ProcedureDoiCho(Var A,B:Point);

Var k : Point;

Begin

k:=A; A:=B; B:=k;

End;

ProcedureReadInp;

Begin

Assign(f,fi); Reset(f);

For i:=1 to 4 do

Read(f,P[i].x,P[i].y);

Close(f);

End;

ProcedureSolve;

Var minx,miny,maxx,maxy:real;

k:boolean;

Begin

For i:=1 to 4 do

For j:=i to 4 do

If P[i].x>P[j].x then DoiCho(P[i],P[j]);

minx:=P[1].x; miny:=P[1].y;

maxx:=P[1].x; maxy:=P[1].y;

For i:=2 to 4 do

Begin

If P[i].xthen minx:=P[i].x;

If P[i].ythen miny:=P[i].y;

If P[i].x>maxx then maxx:=P[i].x;

If P[i].y>maxy then maxy:=P[i].y;

End;

P[5].x:=minx; P[6].x:=minx;

P[7].x:=maxx; P[8].x:=maxx;

P[5].y:=miny; P[8].y:=miny;

P[6].y:=maxy; P[7].y:=maxy;

k:=false;

A[1]:=D(P[1],P[2]);A[2]:=D(P[2],P[4]);

A[3]:=D(P[4],P[3]);A[4]:=D(P[3],P[1]);

A[5]:=D(P[5],P[6]);A[6]:=D(P[6],P[7]);

A[7]:=D(P[7],P[8]);A[8]:=D(P[8],P[5]);

k:=(A[1]=A[2]) and (A[2]=A[3]) and (A[3]=A[4]);

k:= k and (A[5]=A[6]) and (A[6]=A[7]) and(A[7]=A[8]);

Assign(f,fo); Rewrite(f);

If k then Writeln(f,1) elseWriteln(f,-1);

Close(f);

End;

Begin

ReadInp;

Solve;

End.

Bạn đọc có thể tự chứng minh thuật toán trên cho bài toán 2 là đúng. Nếu không thích, bạn cũng có thể kiểm tra góc vuông bằng cách kiểm tra 4 tam giác ABC, BCD, CDA, DAB có phải là 4 tam giác vuông lần lượt tại 4 đỉnh B, C, D, A hay không (bằng định lí Pythagore đảo)...

Bài toán 3. Cho hai điểm A(x_A, y_A) và B(x_B, y_B) không trùng nhau. Hãy tìm toạ độ các điểm C, D, E, F sao cho ABCD và ABEF là các hình vuông.

Sau khi phân tích bài toán này, tôi được kết quả:

Nếu thì toạ độ 4 điểm C, D, E, F sẽ là:

x_C = x_B + (y_B - y_A) ; y_C = y_B – (x_B – x_A).

x_D = x_A + (y_B - y_A) ; y_D = y_A – (x_B – x_A).

x_E = x_B – (y_B - y_A) ; y_E = y_B + (x_B – x_A).

x_F = x_A – (y_B - y_A) ; y_F = y_A + (x_B – x_A).

Với x_A > x_B thì với tính toán như trên, ta sẽ được hai hình vuông ABDC, ABFE (không đúng với đề), do đó chúng ta chỉ cần đảo toạ độ hai điểm C và D cho nhau, E và F cho nhau.

Bài toán 3 là bài toán cho 2 đỉnh kề nhau, xác định 2 đỉnh còn lại của hình vuông. Sau đây là bài toán 4, cho 2 đỉnh đối nhau, xác định 2 đỉnh còn lại của hình vuông.

Bài toán 4. Cho hai điểm A(x_A, y_A) và C(x_C, y_C) là hai đỉnh đối nhau của một hình vuông. Hãy tìm toạ độ các điểm B và D sao cho ABCD là hình vuông.

Input : File HAIDINH.INP gồm 2 dòng là toạ độ 2 đỉnh A và C của hình vuông.

Output : File HAIDINH.OUT gồm 2 dòng là toạ độ 2 đỉnh B và D của hình vuông

(mỗi toạ độ trong file output chính xác đến chữ số thứ 4 sau dấu phẩy).

Ta có nhận xét : Hình vuông có hai đường chéo bằng nhau và vuông góc với nhau tại trung điểm mỗi đường.Ta cần tìm trung điểm của AC, đó là điểm O có toạ độ :

Sau đó, chúng ta phân tích tiếp, được kết quả :

x_B = x_O + (y_A – y_O) ; y_B = y_O + (x_O – x_A)

x_D = x_O – (y_A – y_O) ; y_D = y_O – (x_O – x_A)

Sau đây là chương trình của bài 4.

ProgramTim2Dinh;

Const fi = 'HAIDINH.INP';

fo = 'HAIDINH.OUT';

Type Point = Record

x,y:real;

End;

VarP:Array[1..5] of Point;

f:text;

ProcedureReadInp;

Begin

Assign(f,fi); Reset(f);

Read(f,P[1].x,P[1].y);

Read(f,P[2].x,P[2].y);

Close(f);

End;

ProcedureSolve;

Begin

P[5].x:=(P[1].x+P[2].x)/2;

P[5].y:=(P[1].y+P[2].y)/2;

P[3].x:=P[5].x+(P[1].y-P[5].y);

P[3].y:=P[5].y+(P[5].x-P[1].x);

P[4].x:=P[5].x-(P[1].y-P[5].y);

P[4].y:=P[5].y-(P[5].x-P[1].x);

End;

ProcedureWriteOut;

Begin

Assign(f,fo); Rewrite(f);

Write(f,P[3].x:0:4,' ',P[3].y:0:4);

Writeln(f);

Write(f,P[4].x:0:4,' ',P[4].y:0:4);

Close(f);

End;

Begin

ReadInp;

Solve;

WriteOut;

End.

Chúng ta cùng xem sự phát triển của những bài toán về hình vuông:

Bài toán 5. Hình vuông (Đề thi Tin học trẻ không chuyên toàn quốc 2001 – bảng B).

Cho một lưới N x N điểm gồm N dòng và N cột là các điểm nút của một lưới ô vuông. Các dòng được đánh số từ trên xuống dưới, các cột được đánh số từ trái qua phải bắt đầu từ 1. Trên lưới điểm đó cho một số đoạn thẳng, mỗi đoạn nối một cặp điểm cạnh nhau trên cùng một dòng (đoạn ngang) hoặc trên cùng một cột (đoạn dọc). Cần phải đếm số các hình vuông với kích thước nhất định được tạo thành bởi các đoạn thẳng đã cho của lưới nêu trên.

Chẳng hạn ở hình 4, có 3 hình vuông: hai hình kích thước 1 và một hình kích thước 2 (kích thước của hình vuông là số các đoạn thẳng tạo thành 1 cạnh của hình vuông).

Yêu cầu : Hãy xác định số lượng các loại hình vuông và số hình vuông mỗi loại trong lưới điểm đã cho (các hình vuông có cùng kích thước được xếp vào cùng một loại).

Input : SQUARE.INP

-Dòng đầu tiên chứa 2 số nguyên N là số dòng (số cột) của lưới.

-Dòng thứ hai chứa số nguyên M là số các đoạn thẳng được cho trên lưới.

-M dòng tiếp theo, mỗi dòng biểu diễn một đoạn thẳng, có dạng :

·H i j chỉ một đoạn ngang trên dòng thứ i nối 2 điểm ở cột j và cột j+1

·hoặc V i j chỉ một đoạn dọc trên cột thứ i nối hai điểm ở dòng j và dòng j+1.

Output : SQUARE.OUT

-Dòng đầu tiên ghi số nguyên P là số loại hình vuông có trên lưới.

-P dòng tiếp theo, mỗi dòng ghi thông tin mô tả về một loại hình vuông và số lượng hình vuông loại đó, bao gồm hai số nguyên a và b cho biết có a hình vuông có cạnh độ dài b. Các thông tin về các loại hình vuông phải được đưa ra theo thứ tự tăng dần của độ dài cạnh.

-Trong trường hợp không tìm được bất cứ một hình vuông nào thì ghi duy nhất một dòng thông báo : NO SQUARE.

Ví dụ : (Theo hình 4)

Ở bài này, chúng ta không chỉ kiểm tra hình vuông thông qua các đỉnh mà còn phải kiểm tra các đoạn nối giữa chúng nữa.

Việc đầu tiên là tổ chức dữ liệu như thế nào cho hợp lí. Chúng ta sẽ đặt toạ độ nút ở hàng i, cột j là(i, j) với . Như vậy nút ở góc trên trái có toạ độ (1, 1), nút góc dưới, phải sẽ là (N, N). Ta sẽ sử dụng 1 mảng C : Array[1..9,1..9,1..2] of boolean để lưu các cạnh, trong đó :

• C[i,j,1] = True / False nếu có / không có đoạn nối ngang giữa nút (i, j) và nút (i, j+1).
• C[i,j,2] = True / False nếu có / không có đoạn nối dọc giữa nút (i, j) và nút (i+1, j).

Hiển nhiên, C[i,N,1] = False với mọi i và C[N,i,2] = False với mọi i.

Ta sử dụng mảng HV[1..9] để chỉ số hình vuông mà cạnh có độ dài là 1 đoạn, 2 đoạn, …, N đoạn.

Một “ý tưởng táo bạo” là vét cạn toàn bộ để tìm ra tất cả các bộ 4 điểm rồi kiểm tra. Tuy nhiên, ý tưởng này không được khả thi cho lắm. Chúng ta có thể đi theo giải pháp sau :

Tại mỗi nút (i,j) với i

For i:=1 to N do

For j:=1 to N do

Begin

max:=i;

If max

For d:=1 to N-max do

If KT(i,j,d) then Inc(HV[d]);

End;

Kèm theo đó, chúng ta phải có hàm KT(i,j,d) trả về giá trị Boolean để kiểm tra xem nút (i,j) có thể là đỉnh trên trái của hình vuông mà cạnh có độ dài d đoạn hay không. Như vậy, chương trình hoàn chỉnh của bài 5 là :

ProgramSquare;

Const fi = 'SQUARE.INP';

fo = 'SQUARE.OUT';

Vari,j,d,max,N,M,P:byte;

HV : Array[1..9] of integer;

C : Array[1..9,1..9,1..2] of boolean;

f:text;

ProcedureReadInp;

Var a,b:byte; ch:char;

Begin

Fillchar(C,sizeof(C),false);

Fillchar(HV,sizeof(HV),0);

P:=0;

Assign(f,fi); Reset(f);

Readln(f,N);

Readln(f,M);

For i:=1 to M do

Begin

Readln(f,ch,a,b);

If ch='H' then C[a,b,1]:=True;

If ch='V' then C[b,a,2]:=True;

End;

Close(f);

End;

FunctionKT(i,j,d:byte):boolean;

Label Ra;

Var a:byte; k:boolean;

Begin

k:=true;

For a:=i to i+d-1 do {Kiểm tra những đoạn dọc}

Begin

If C[a,j,2] = false then

Begin

k:=false; Goto Ra;

End;

If C[a,j+d,2] = false then

Begin

k:=false; Goto Ra;

End;

End;

For a:=j to j+d-1 do {Kiểm tra những đoạn ngang}

Begin

If C[i,a,1] = false then

Begin

k:=false; Goto Ra;

End;

If C[i+d,a,1] = false then

Begin

k:=false; Goto Ra;

End;

End;

Ra : KT:=k;

End;

ProcedureSolve;

Begin

For i:=1 to N do

For j:=1 to N do

Begin

max:=i;

If maxthen max:=j;

For d:=1 to N-max do

If KT(i,j,d) then Inc(HV[d]);

End;

End;

ProcedureWriteOut;

Begin

For i:=1 to N do

If HV[i]>0 then inc(P);

Assign(f,fo); Rewrite(f);

Writeln(f,P);

For i:=1 to N do

If HV[i]>0 then Writeln(f,HV[i],' ',i);

Close(f);

End;

Begin

ReadInp; Solve; WriteOut;

End.

Sau đây là hai bài tập dành cho bạn tự luyện tập:

Bài 6. Hình vuông (Đề thi tuyển sinh lớp 10 chuyên Tin – Năm học 2003 – 2004 - PTNK)

Trên mặt phẳng, cho N hình vuông có cạnh song song với trục toạ độ được đánh số từ 1 đến N . Hình vuông thứ i được cho bởi toạ độ góc dưới trái (x_i, y_i) và toạ độ đỉnh trên phải (z_i, t_i). Toạ độ các đỉnh là số nguyên trong phạm vi từ –10000 đến 10000. Khoảng cách giữa hai hình vuông A và B được định nghĩa là độ dài của đoạn thẳng ngắn nhất trong số các đoạn thẳng mà một đầu mút thuộc hình vuông A còn đầu mút kia thuộc hình vuông B.

Yêu cầu: Tìm 2 hình vuông xa nhau nhất trong N hình vuông cho trước.

Input: Vào từ file văn bản SQUARE.INP trong đó dòng đầu chứa số N, dòng thứ i trong N dòng tiếp theo chứa 4 số x_i, y_i, z_i, t_i.

Output: Ghi ra file văn bản SQUARE.OUT trong đó chứa chỉ số của 2 hình vuông tìm được.

Ví dụ:

Bài 7. Lưới ô vuông (Đề thi Tin học trẻ không chuyên Toàn quốc 2002 - Bảng C)

Cho một lưới ô vuông có kích thước m dòng, n cột . Các dòng của lưới được đánh số từ 1 đến m từ trên xuống dưới, các cột của lưới được đánh số từ 1 đến n từ trái sang phải. Ô nằm trên dòng i, cột j là ô (i,j) của lưới và (i,j) gọi là toạ độ của ô này.

Một nhóm gồm p học sinh tổ chức trò chơi đánh dấu như sau : Mỗi học sinh đánh dấu các ô của một hình chữ nhật trên lưới. Các hình chữ nhật này có thể giao nhau. Một tập S các ô của lưới ô vuông đã cho gọi là miền liên thông bậc k nếu thoả 2 điều kiện :

• Mỗi ô thuộc S có số lượng học sinh đánh dấu nó đúng bằng k.
• Hoặc S có đúng 1 ô, hoặc nếu S có nhiều hơn 1 ô thì đối với 2 ô bất kì của S luôn có cách di chuyển qua các ô chung cạnh thuộc S để từ ô này đến ô kia.

Yêu cầu: Hãy đếm số miền liên thông bậc k = 1, 2, …, p

Input: File SQNET.INP: Dòng đầu tiên chứa 2 số nguyên m, n là kích thước của lưới. Dòng thứ hai chứa p là số học sinh. Dòng thứ i trong số p dòng tiếp theo chứa thông tin về hình chữ nhật mà học sinh thứ i chọn, gồm 4 số nguyên dương x, y, u, v, trong đó (x,y) là toạ độ ô góc trên trái và (u,v) là toạ độ ô góc dưới phải của hình chữ nhật.

Output: Ghi ra file SQNET.OUT, gồm p dòng, dòng thứ i chứa số lượng miền liên thông bậc i.

Ví dụ :

School@net