PHƯƠNG PHÁP GIẢI TOÁN HÌNH HỌC BẰNG NNLT PASCAL
I. KHÁI NIỆM HÌNH HỌC VÀ CÁC ĐỐI TƯỢNG HÌNH HỌC CƠ BẢN
1. Khái niệm hình học
Đ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 toá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 toán.
Các bài toá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 toá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 to¸n kiÓm tra mét ®iÓm cã n»m trong ®a gi¸c hay kh«ng?
2. Đối tượng hình học cơ bản.
Trong các bài toá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.
3. Dữ liệu lưu trữ các đối tượng hình học cơ bản
Type
point = record x,y: integer; end;
Line = record p1,p2: point; end;
Var Polygon: Array[0..Nmax] of Point;
II. MỘT SỐ PHÉP TOÁN CƠ BẢN
1. Vị trí tương đối của điểm so với đường thẳng, tia và đoạn thẳng
Bài toán 1: Cho điểm M(x0,y0), A(xA,yA), B(xB,yB). 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
Phương pháp:
Đặt F(X,Y) = (yA-yB)X + (xB-xA)Y + (xAyB - xByA)
- Điểm M thuộc đường thẳng AB khi F(x0,y0) = 0
- Điểm M thuộc đoạn thẳng AB khi:
F(x0,y0)=0 và Min(xA,xB)x0 Max(xA,xB) và Min(yA,yB) y0 Max(yA,yB)
- Điểm M thuộc tia AB khi F(x0,y0) = 0 và có nghĩa là M phải thoả mãn điều kiện: F(x0,y0) = 0 và (x0-xA)(xB-xA)0 và (y0-yA)(yB-yA)0
Chương trình:
var xa,ya,xb,yb,xo,yo:real;
procedure nhap;
begin
repeat
write('nhap toa do diem A:'); readln(xa,ya);
write('nhap toa do diem B:'); readln(xb,yb);
until (xa<>xb) or (ya<>yb);
write('nhap toa do diem M:'); readln(xo,yo);
end;
{=============}
Function F(xo,yo:real):real;
begin
F:= (ya-yb)*xo+(xb-xa)*yo +(xa*yb - xb*ya);
end;
{=============}
Function Max(a,b:real):Real;
begin
if a>b then Max:=a else Max:=b;
end;
{=============}
Function Min(a,b:real):Real;
begin
if a>b then Min:=b else Min:=a;
end;
{====Kiem tra M thuoc duong thang, doan thang, tia===}
Begin
nhap;
if F(xo,yo)=0 then writeln('M thuoc duong thang AB')
else writeln('M ko thuoc duong AB');
if (F(xo,yo)=0) and (min(xa,xb)<=xo) and (xo<=max(xa,xb)) and (min(ya,yb)<=yo) and (yo<=max(ya,yb))
then writeln('M thuoc doan thang AB') else writeln('M khong thuoc doan thang AB');
if (F(xo,yo)=0) and ((xo-xa)*(xb-xa)>=0) and ((yo-ya)*(yb-ya)>=0)
then writeln('M thuoc tia AB') else writeln('M khong thuoc tia AB');
readln;
End.
2. Giao của các đoạn thẳng, đường thẳng và tia
Bài toán 2. Cho 2 đường thẳng có phương trình a1x+b1y+c1=0 và a2x+b2y+c2=0. Tìm giao điểm (nếu có) của 2 đường thẳng trên.
Phương pháp:
B1. Tính D = a1b2 - a2b1, Dx = c2b1 - c1b2, Dy = a2c1 - a1c2
B2. Xét 3 khả năng:
+ Nếu D=Dx=Dy=0 thì kết luận 2 đường thẳng trùng nhau
+ Nếu D=0 và ((Dx0) hoặc (Dy0)) thì kết luận 2 đường thẳng song song
+ Nếu D0 thì kết luận 2 đường thẳng cắt nhau tại điểm có (Dx/D, Dy/D)
Chương trình:
var a1,b1,c1,a2,b2,c2,D,Dx,Dy:real;
{============}
procedure nhap;
begin
write('nhap he so cua dt 1 a1,b1,c1:'); readln(a1,b1,c1);
write('nhap he so cua dt 2 a2,b2,c2:'); readln(a2,b2,c2);
end;
{=============}
Begin
nhap;
D:=a1*b2-a2*b1; Dx:=c2*b1-c1*b2; Dy:=a2*c1-a1*c2;
if (D=0)and(Dx=0)and(Dy=0) then write('2 duong thang trung nhau')
else
if (D=0)and((Dx<>0)or(Dy<>0)) then write('2 duong thang song song')
else write('2 d/thang cat nhau tai M(',Dx/D:5:2,',',Dy/D:5:2,')');
readln;
End.
Bài toán 3. Cho 2 đoạn thẳng AB và CD với A(x1,y1), B(x2,y2), C(x3,y3), D(x4,y4). Tìm giao điểm (nếu có) của 2 đoạn thẳng
Phương pháp:
B1. Tìm giao điểm M của 2 đường thẳng AB và CD
B2. 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ó.
Chương trình:
var xa,ya,xb,yb,xc,yc,xd,yd:real; a1,b1,c1,a2,b2,c2,D,Dx,Dy:real;
{============}
procedure nhap;
begin
repeat
write('nhap toa do diem A:'); readln(xa,ya);
write('nhap toa do diem B:'); readln(xb,yb);
write('nhap toa do diem C:'); readln(xc,yc);
write('nhap toa do diem D:'); readln(xd,yd);
until ((xa<>xb) or (ya<>yb)) and ((xa<>xb) or (ya<>yb));
end;
{=============}
Function Max(a,b:real):Real;
begin
if a>b then Max:=a else Max:=b;
end;
{=============}
Function Min(a,b:real):Real;
begin
if a>b then Min:=b else Min:=a;
end;
{===Kiem tra M thuoc doan ==}
Function Ktra(xo,yo,xa,ya,xb,yb:real):boolean;
begin
if (min(xa,xb)<=xo) and (xo<=max(xa,xb))
and (min(ya,yb)<=yo) and (yo<=max(ya,yb))
then Ktra:=true else Ktra:=false;
end;
{===Tim giao diem neu co ===}
procedure Xac_dinh;
begin
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;
if(D<>0)and(ktra(Dx/D,Dy/D,xa,ya,xb,yb))and ktra(Dx/D,Dy/D,xc,yc,xd,yd))
then writeln('2 d/thang cat nhau tai M(',Dx/D:5:2,',',Dy/D:5:2,')')
else write('Hai doan thang khong cat nhau');
end;
{==============}
Begin
nhap;
Xac_dinh;
readln;
End.
Bài toán 4. Cho tia AM chứa điểm B (khác A) và đoạn thẳng CD với A(x1,y1), B(x2,y2), C(x3,y3), D(x4,y4). Tìm giao điểm (nếu có) của tia AM với đoạn thẳng CD.
Phương pháp:
B1. Tìm giao điểm N của 2 đường thẳng AB và CD
B2. 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ó.
Chương trình:
var xa,ya,xb,yb,xc,yc,xd,yd:real; a1,b1,c1,a2,b2,c2,D,Dx,Dy:real;
{============}
procedure nhap;
begin
repeat
write('nhap toa do diem A:'); readln(xa,ya);
write('nhap toa do diem B:'); readln(xb,yb);
write('nhap toa do diem C:'); readln(xc,yc);
write('nhap toa do diem D:'); readln(xd,yd);
until ((xa<>xb) or (ya<>yb)) and ((xa<>xb) or (ya<>yb));
end;
{=============}
Function Max(a,b:real):Real;
begin
if a>b then Max:=a else Max:=b;
end;
{=============}
Function Min(a,b:real):Real;
begin
if a>b then Min:=b else Min:=a;
end;
{===Kiem tra M thuoc doan ==}
Function Ktra(xo,yo,xa,ya,xb,yb:real):boolean;
begin
if (min(xa,xb)<=xo) and (xo<=max(xa,xb))
and (min(ya,yb)<=yo) and (yo<=max(ya,yb))
then Ktra:=true else Ktra:=false;
end;
{===Tim giao diem===}
procedure Xac_dinh;
begin
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;
if (D<>0) and (ktra(Dx/D,Dy/D,xc,yc,xd,yd))
and ((Dx/D-xa)*(xb-xa)>=0) and ((Dy/D-ya)*(yb-ya)>=0)
then writeln('Tia AM cat doan thang CD tai M(',Dx/D:5:2,',',Dy/D:5:2,')')
else write('Tia AM khong cat doan thang CD');
end;
{==============}
Begin
nhap;
Xac_dinh;
readln;
End.
3. Vị trí của điểm so với đa giác
Bài toán 5. Cho đa giác gồm N đỉnh d1, d2,...,dN 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:
B1. 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
B2. Kẻ MN song song với trục hoành (điểm N có hoành độ lớn hơn max hoành độ của đa giác)
B3. 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
+ Đỉnh d[i] và d[i+1] không thuộc MN và cạnh (d[i],d[i+1]) cắt đoạn thẳng MN
III. MỘT SỐ DẠNG BÀI TOÁN HÌNH HỌC THƯỜNG GẶP
Dạng 1. Mối quan hệ giữa điểm, đoạn thẳng, đa giác.
Phương pháp: Đâ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 toá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)
VD1. Ba điểm thẳng hàng
DL.
NP
KQ.OUT
6
0 0
0 1
0 2
1 1
1 2
2 2
3
Cho N điểm, hãy kiểm tra xem có bao nhiêu bộ 3 điểm thẳng hàng.
Input: 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.
Output: 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.
(Giới hạn: 1<=N<=2000, toạ độ các điểm có giá trị tuyệt đối không quá 10000)
Chương trình:
const maxn=2000;
type td=record x,y:integer; end;
var a: array[1..maxn] of td;
free:array[1..maxn] of boolean;
n,i:integer; c:longint; f:text;
{=======================================}
Procedure DocDL;
begin
assign(f,'DL.INP'); reset(f); readln(f,n);
for i:=1 to n do readln(f,a[i].x,a[i].y);
close(f);
end;
{======================================}
Procedure Dem;
var j,k,x1,y1,tmp:integer;
begin
c:=0;
for i:=1 to n-1 do
begin
fillchar(free,sizeof(free),true);
for j:=i+1 to n-1 do
if free[j] then
begin
tmp:=1;
x1:=a[j].x-a[i].x; y1:=a[j].y-a[i].y;
for k:=j+1 to n do
if free[k] then
if x1*(a[k].y-a[i].y)=y1*(a[k].x-a[i].x) then
begin
inc(tmp);
free[k]:=false;
end;
inc(c,tmp*(tmp-1) div 2);
end;
end;
end;
{========================================}
procedure Xuat;
begin
assign(f,'KQ.OUT'); rewrite(f); writeln(f,c); close(f);
end;
{====================================}
Begin
DocDL; Dem; Xuat;
End.
VD2. Đường thẳng cắt nhau
Cho n đường thẳng AiBi (1in) phân biệt với A i, 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.
DL.INP
KÕt qu¶
0 0 1 1
0 1 1 2
-1 -1 8 9
§/th¼ng 1 c¾t ®/th¼ng 3
§/th¼ng 2 c¾t ®/th¼ng 3
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.
Ý tưởng:
- 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:
type dthang=record x1,y1,x2,y2:integer; end;
heso=record a,b,c:integer; end;
var pt:array[1..100] of heso;
f:text; n:integer;
{============}
procedure doc_DL;
var i,x1,y1,x2,y2:integer;
begin
i:=0;
assign(f,'dt.inp');reset(f);
while not eof(f) do
begin
i:=i+1;
readln(f,x1,y1,x2,y2);
pt[i].a:=(y1-y2);
pt[i].b:=(x2-x1) ;
pt[i].c:=x1*y2-x2*y1;
end;
n:=i;
close(f);
end;
{===Kiem tra 2 duong thang cat nhau ==}
Function Ktra(pt1,pt2:heso):boolean;
var D:integer;
begin
D:=pt1.a*pt2.b-pt2.a*pt1.b;
if D<>0 then ktra:=true else Ktra:=false;
end;
{===Tim giao diem===}
procedure Xac_dinh;
var i,j:integer; kt:boolean;
begin
kt:=false;
For i:=1 to n-1 do
For j:=i+1 to n do
if ktra(pt[i],pt[j]) then
begin
writeln('Duong thang',i,'cat duong thang',j);
kt:=true;
end;
if not kt then writeln('khong co cap duong thang cat nhau')
end;
{==============}
Begin
doc_DL;
Xac_dinh;
readln;
End.
VD3. Điểm thuộc đa giác.
Cho đa giác không tự cắt A1A2...AN với các đỉnh Ai(xi,yi) nguyên. Với điểm A(xA,yA) cho trước, hãy xác định xem A có nằm trong đa giác đã cho hay không (Trong trường hợp trên cạnh đa giác xem như nằm trong đa giác)
Dagiac.inp
KÕt qu¶
5
0 0
2 0
0 3
-2 2
-3 -2
10 10
§iÓm A(10,10)
kh«ng n»m trong ®a gi¸c
Dữ liệu: 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ố nguyên.
Kết quả: Đư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 D0 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.
- Điểm N thuộc đoạn thẳng CD khi: Min(xC,xD)xN Max(xC,xD) và Min(yC,yD) yN Max(yC,yD)
- Đ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
Chương trình:
const maxn=100;
Type xy=record x,y:real; end;
var n:byte;
A:array[1..maxn+2] of xy;
a1,a2,x1,x2,y1,y2,b1,b2, c1,c2,D,Dx,Dy:Real;
k,dem,dem1,i:integer;
{===================================}
procedure Doc_DL;
var f:text;
begin
assign(f,'DL.INP'); reset(f); readln(f,n);
fillchar(A,Sizeof(A),0);
for i:=1 to n do readln(f,A[i].x,A[i].y);
readln(f,A[N+2].x,A[n+2].y);
A[n+1]:=A[1]; close(f);
end;
{======================================}
function kiemtradinh:boolean;
begin
kiemtradinh:=true;
for i:=1 to n do
if (A[i].x=A[n+2].x) and (A[i].y=A[n+2].y) then exit;
kiemtradinh:=false;
end;
{========================================}
function kiemtracanh:boolean;
begin
kiemtracanh:=true;
for i:=1 to n do
if A[n+2].x*(A[i].y-A[i+1].y)+A[n+2].y*(A[i+1].x-A[i].x)
+ A[i].x*A[i+1].y-A[i].y*A[i+1].x=0 then exit;
kiemtracanh:=false;
end;
{=============================================}
{=== Kiem tra Ax co chua canh da giac hay cat canh da giac===}
Function kiemtra_giaodiem(xo,yo,xc,yc,xd,yd:real):boolean;
var xa,ya,xb,yb:real;
{===Kiem tra diem thuoc doan thuoc doan ==}
Function Ktra(xo,yo,xa,ya,xb,yb:real):boolean;
var max1,min1,max2,min2:real;
begin
if xa>xb then begin Max1:=xa;min1:=xb end else begin Max1:=xb;min1:=xa; end;
if ya>yb then begin Max2:=ya;min2:=yb end else begin Max2:=yb;min2:=ya; end;
if (min1<=xo) and (xo<=max1) and (min2<=yo) and (yo<=max2)
then Ktra:=true else Ktra:=false;
end;
{===Tim giao diem===}
begin
xa:=xo;ya:=yo;xb:=xo+1;yb:=yo; 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;
if ((D<>0) and (ktra(Dx/D,Dy/D,xc,yc,xd,yd)) and ((Dx/D-xa)*(xb-xa)>=0) and ((Dy/D-ya)*(yb-ya)>=0))
or ((yc=yd)and(yc=yo))
then kiemtra_giaodiem:=true else kiemtra_giaodiem:=false;
end;
{====================================}
function kiemtra:boolean;
begin
kiemtra:=true;
if kiemtradinh then exit;
if kiemtracanh then exit;
dem:=0; dem1:=0;
for i:=1 to n do
if kiemtra_giaodiem(A[N+2].x,A[n+2].y,A[i].x,A[i].y,A[i+1].x,A[i+1].y) then Dem:=dem+1;
if dem mod 2=0 then kiemtra:=false;
end;
{==================================================}
BEGIN
Doc_DL;
if kiemtra then
write('Diem A(',a[n+2].x:0:2,',',A[n+2].y:0:2,') nam trong da giac')
else write('Diem A(',a[n+2].x:0:2,',',A[n+2].y:0:2,') khong nam trong da giac');
readln;
end.
VD4. Đếm số điểm có toạ độ nguyên thuộc đa giác (Bài đã được đăng trên tạp chí Tin học & Nhà trường số 04/2009)
DL.INP
KQ.OUT
4
0 0
3 3
4 0
2 1
8
Cho đa giác gồm n đỉnh (x1,y1), (x2,y2), ..., (xn,yn), biết (2<n<104), 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ố nguyên 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:
- Xác định số điểm có toạ độ nguyên: Sđ=round(abs(a/2)+b/2+1)
Chương trình:
Var N:longint; f:text;
x1,y1,xt,yt,x,y,i,b,sd,a:longint;
{================================}
Function UCLN(a,b:longint):longint;
var tg:longint;
begin
while b>0 do
begin tg:=b; b:=a mod b; a:=tg; end;
UCLN:=a;
end;
{==========================================}
BEGIN
b:=0; a:=0;
assign(f,'dagiac.inp'); reset(f);
readln(f,n); readln(f,x,y);
x1:=x; y1:=y;
for i:=2 to n do
begin
xt:=x; yt:=y;
readln(f,x,y);
a:=a+(x-xt)*(y+yt);b:=b+UCLN(abs(x-xt),abs(y-yt));
end;
a:=a+(x1-x)*(y1+y);
b:=b+UCLN(abs(x1-x),abs(y1-y));
sd:=round(abs(a/2)+b/2+1);
writeln(sd);
close(f);
readln;
END.
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:
S =
- Nếu đa giác là hình chữ nhật (n=4) có các cạnh là a,b thì diện tích là: S=ab
- Nếu đa giác là hình vuông (n=4) có cạnh là a thì diện tích là: S=a2
- 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
DL.INP
KQ
5
- 8 -8 0 0 1 0 -2 4 -5 0
44.00
- Dòng 2: Chứa 2xN số nguyên dương x1 y1 x2 y2...xN yN là 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:
- Lưu toạ độ các đỉnh đa giác vào mảng toado
- Sử dụng công thức tính diện tích đa giác:
for i:=1 to n do
s:=s+(Toado[i+1].x-Toado[i].x)*(Toado[i+1].y+toado[i].y)/2;
- Kết quả cần tìm là abs(s)
Chương trình:
const maxn=100;
type xy=record
x,y:integer; end;
var Toado:array[1..maxn+1] of xy;
n,i:integer; s:real;
Procedure Nhap;
var f:text;
begin
assign(f,'DL.TXT');
reset(f);
readln(f,n);
for i:=1 to n do read(f,Toado[i].x,toado[i].y);
close(f);
end;
{====================================}
procedure Dientich;
begin
s:=0;
Toado[n+1].x:=Toado[1].x;
Toado[n+1].y:=Toado[1].y;
for i:=1 to n do
s:=s+(Toado[i+1].x-Toado[i].x)*(Toado[i+1].y+toado[i].y)/2;
writeln('Dien tich da giac :', abs(s):0:2);
readln;
end;
Begin
Nhap;
Dientich;
End.
VD2. D·y h×nh ch÷ nhËt
HCN.inp
HCN.out
5
-3 -4 0 -2
-6 -4 0 0
-6 -2 -3 0
0 0 7 7
-6 0 0 7
-3 -4 0 -2
-6 -2 -3 0
-6 -4 0 0
-6 0 0 7
0 0 7 7
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 (1iN): 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)
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:
- Lu to¹ ®é c¸c ®Ønh ®a gi¸c vµo m¶ng a
- 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
Ch¬ng tr×nh:
Type hcn=record x1,y1,x2,y2:integer; end;
var a:array[1..100] of hcn;
n:integer; f:text;
{=================}
procedure doc_dl;
var i:integer;
begin
assign(f,'HCN.inp'); reset(f); readln(f,n);
for i:=1 to n do readln(f,a[i].x1,a[i].y1,a[i].x2,a[i].y2);
close(f);
end;
{=================}
Function S(k:integer):longint;
begin
S:=abs((a[k].x2-a[k].x1)*(a[k].y2-a[k].y1));
end;
{=================}
procedure sapxep;
var i,j:integer;tg:hcn;
begin
for i:=1 to n-1 do
for j:=i+1 to n do
if s(i)>s(j) then
begin tg:=a[i]; a[i]:=a[j]; a[j]:=tg; end;
end;
{================}
procedure ketqua;
var i:integer;
begin
assign(f,'HCN.out'); rewrite(f);
for i:=1 to n do writeln(f,a[i].x1,' ',a[i].y1,' ',a[i].x2,' ',a[i].y2);
close(f);
end;
{===============}
begin
doc_dl; sapxep; ketqua;
end.
Dạng 3. Xác định diện tích phủ bởi các hình chữ nhật
Phương pháp: 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 hoà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
Bíc 3. 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 1in-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.
VD1. DiÖn tÝch phñ bëi c¸c h×nh ch÷ nhËt (Bµi ®· ®îc ®¨ng trªn t¹p chÝ Tin häc & Nhµ trêng sè 02/2009)
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.
HCN.inp
Kết quả
5
-3 -4 0 -2
-6 -4 0 0
-6 -2 -3 0
0 0 7 7
-6 0 0 7
115
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 (1iN): 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.
Kết quả: Đư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.
Ý tưởng:
- 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
- Lu 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 1in-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.
Const Maxn=1000;
Type Toa_do = record x1,y1,x2,y2:integer; end;
mang=array[1..2*maxn] of integer;
var N,s:integer;
a:array[1..maxn] of toa_do;
X,Y:mang;
{=======Doc du lieu=====}
Procedure doc_dl;
var f:text; i:integer;
begin
assign(f,'HCN.inp'); reset(f);
readln(f,n);
for i:=1 to n do
readln(f,a[i].x1,a[i].y1,a[i].x2,a[i].y2);
close(f);
end;
{===Sap xep mang tang dan===}
Procedure Sapxep(Var T:Mang);
Var i,j,TG,m:integer;
Begin
m:=2*n;
for i:=1 to m-1 do
for j:=i+1 to m do
if T[i]>T[j] then
begin
TG:=T[i];
T[i]:=T[j];
T[j]:=TG;
end;
end;
{====Kiem tra HCN moi thuoc HCN da cho====}
function Kiemtra_thuoc(i,j:integer):boolean;
var k:integer;
begin
Kiemtra_thuoc:=true;
for k:=1 to N do
if (a[k].x1<=x[i-1]) and (X[i]<=a[k].x2)
and (a[k].y1<=y[j-1]) and(Y[j]<=a[k].y2) then exit;
Kiemtra_thuoc:=false;
end;
{========================================}
Procedure Xuly;
var i,j:integer;
Begin
for i:=1 to N do
begin
X[i*2-1]:=a[i].x1;
X[i*2]:=a[i].x2;
Y[i*2-1]:=a[i].y1;
Y[i*2]:=a[i].y2;
end;
Sapxep(X); Sapxep(Y);
for i:=2 to 2*N do
for j:=2 to 2*N do
if Kiemtra_thuoc(i,j) then S:=s+(X[i]-X[i-1])*(Y[j]-Y[j-1]);
end;
{====================================}
Begin
doc_dl;
s:=0;
Xuly;
Write('Dien tich la: ', S);
readln;
End.
VD2. 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.
PhuCN.INP
PhuCN.OUT
3
10 30 40 10
20 20 60 0
0 40 30 0
0 40 60 0
500
Dữ liệu vào: Đọ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 quá 100.
Kết quả: Ghi ra tệp văn bản PHUCN.OUT
- 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 hoà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
Chương trình:
const maxn=1000;
Type Toa_do=record x1,y1,x2,y2:integer; end;
mang=array[1..2*maxn] of integer;
var N, s,s1,maxx,minx,maxy,miny:integer;
a:array[1..maxn] of toa_do;
x,y:mang;f:text;
{================Doc DL===============}
Procedure DocDL;
var f:text; i:integer;
begin
Assign(f,'HCN.Inp'); reset(f);
readln(f,n);
minx:=maxint; maxx:=-maxint; miny:=maxint; maxy:=-maxint;
for i:=1 to n do
begin
readln(f,a[i].x1,a[i].y1,a[i].x2,a[i].y2);
if a[i].x1<minx then minx:=a[i].x1;
if a[i].x2<minx then minx:=a[i].x2;
if a[i].y1<miny then miny:=a[i].y1;
if a[i].y2<miny then miny:=a[i].y2;
if a[i].x1>maxx then maxx:=a[i].x1;
if a[i].x2>maxx then maxx:=a[i].x2;
if a[i].y1>maxy then maxy:=a[i].y1;
if a[i].y2>maxy then maxy:=a[i].y2;
end;
close(f);
end;
{=================Sap xep mang tang dan=========}
Procedure sapxep(var t:mang);
var i,j,TG,m:integer;
begin
m:=2*n;
for i:=1 to m-1 do
for j:=i+1 to m do
if T[i]>T[j] then
begin
TG:=t[i];
T[i]:=T[j];
T[j]:=TG;
end;
end;
{========Kiem tra HCN moi thuoc HCN da cho===========}
function Kiemtra_Thuoc(i,j:integer):boolean;
var k:integer;
begin
kiemtra_thuoc:=true;
for k:=1 to n do
if (a[k].x1<=x[i-1]) and (x[i]<=a[k].x2)
and (a[k].y1<=y[j-1]) and (y[j]<=a[k].y2) then exit;
kiemtra_thuoc:=false;
end;
{=========Xu ly bai toan===========}
Procedure Xuly;
var i,j:integer;
begin
for i:=1 to n do
begin
X[i*2-1]:=a[i].x1;
X[2*i]:=a[i].x2;
Y[i*2-1]:=a[i].y1;
Y[2*i]:=a[i].y2;
end;
sapxep(X); sapxep(Y);
for i:=2 to 2*n do
for j:=2 to 2*n do
if kiemtra_thuoc(i,j) then s:=s+(x[i]-x[i-1])*(y[j]-y[j-1]);
writeln(s);
end;
{=========================================}
begin
s:=0;
docdl;
xuly;
assign(f,'HCN.out'); rewrite(f);
writeln(f,minx,' ',maxy,' ',maxx,' ',miny);
writeln(f,s);
s1:=abs(maxx-minx)*(maxy-miny)-s;
writeln(f,s1);
close(f);
end.
VD3. Diện tích phủ bởi các hình tròn
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.
Dữ liệu: 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)
INP.BL3
KÕt qu¶:
3
0 0 5
1 1 5
7 0 1
Dien tich: 95.60
Kết quả: Xuất ra màn hình
Ý tưởng:
- 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 toàn bộ N hình tròn
- Chia hình chữ nhật này thành lưới các ô vuông 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
program Hinh_tron;
type DT=record x,y,r:longint end;
var a:array[1..100] of DT; s:real;
N,i,j,k,i1,j1,x1,y1,x2,y2:longint;
{==========================}
procedure nhap;
var f:text;
begin
assign(f,'Hinhtron.inp'); reset(f);
readln(f,n);
fillchar(a,sizeof(a),0);
for i:=1 to n do readln(f,a[i].x,a[i].y,a[i].r);
close(f);
end;
{==========================}
function kiemtra(x,y:real):boolean;
begin
kiemtra:=true;
for k:=1 to n do
if(sqr(x-a[k].x) +sqr(y-a[k].y)<=sqr(a[k].r)) then exit;
kiemtra:=false;
end;
{==========================}
procedure tinh;
begin
s:=0.0;
x1:=+maxint; y1:=x1; x2:=-maxint; y2:=x2;
for i:=1 to n do
with a[i] do
begin
if x1<x1+r then x1:=x-r;
if y1<y1+r then y1:=y-r;
if x2<x+r then x2:=x+r;
if y2<y+r then y2:=y+r;
end;
for i:=x1 to x2 do
for i1:=0 to 9 do
for j:=y1 to y2 do
for j1:=0 to 9 do
if kiemtra(i+i1*0.1,j+j1*0.1) then s:=s+0.01;
writeln('dien tich:',s:0:2);
end;
{===========================}
begin
nhap;
tinh;
readln;
end.
Dạng 4. Xác định đa giác nhỏ nhất bao tất cả các điểm, đa giác đã cho
Phương pháp: 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 toá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.
VD1. Đa giác không tự cắt
HCN.inp
HCN.out
5
0 1
4 4
0 4
4 0
2 2
4 15.12 14.00
4 4
0 4
0 1
4 0
Cho N điểm A1, A2, ..., AN trên mặt phẳng. Các điểm đều có toạ độ nguyên 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.
Dữ liệu: cho trong tệp HCN.INP gồm n+1 dòng
+ Dòng 1: Chứa số N
+ Dòng i+1 (1 i N): Ghi 2 chữ số nguyên xi,y i là toạ độ đỉnh Ai.
Các số trên cùng một dòng cách nhau một khoảng trắng.
Kết quả: 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.
Ý tưởng:
- Tìm điểm có tung độ nhỏ nhất. Điểm đó sẽ là đỉnh đa giác
- 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.
program dagiac;
type diem=record x,y:integer; end;
var n,i,m:integer;
DG:array[1..100] of diem;
L:array[1..100] of byte;
{============================}
procedure docDL;
var f:text;
begin
assign(f,'bai1.inp');
reset(f);
readln(f,n);
for i:=1 to n do readln(f,DG[i].x,DG[i].y);
close(f);
end;
{============================}
function Goc(p1,p2:diem):real;
var dx,dy,ax,ay:integer; t:real;
begin
dx:=p2.x-p1.x; ax:=abs(dx);
dy:=p2.y-p1.y; ay:=abs(dy);
if (dx=0) and (dy=0) then t:=0 else t:=dy/(ax+ay);
if dx<0 then t:=2-t else if dy<0 then t:=4+t;
Goc:=90*t;
end;
{============================}
function Thuchien:integer;
var min,m:integer; minangle,v:real; t:diem;
begin
min:=1;
for i:=2 to n do
if DG[i].y <DG[min].y then min:=i;
m:=0; DG[n+1]:=DG[min]; minangle:=0.0;
repeat
m:=m+1; t:=DG[m]; DG[m]:=DG[min]; DG[min]:=t;
min:=n+1; v:=minangle; minangle:=360.0;
for i:=m+1 to n+1 do
if goc(DG[m],DG[i])>v then
if goc(DG[m],DG[i])<minangle then
begin
min:=i;
minangle:= goc(DG[m],DG[min]);
L[m]:=i;
end;
until min=n+1;
thuchien:=m;
end;
{===========================}
procedure xuat;
var f:text; v,s:real;
begin
assign(f,'bai1.out');
rewrite(f);
write(f,thuchien,' ');
L[m+1]:=L[1];
V:=0;
DG[L[n+1]].x:=DG[L[1]].x;
DG[L[n+1]].y:=DG[L[1]].y;
for i:=1 to m do v:=v+sqrt(sqr(DG[L[i]].x-DG[L[i+1]].x) + sqr(DG[L[i]].y-DG[L[i+1]].y));
S:=0;
for i:=1 to m do
s:=s+(DG[L[i+1]].x-DG[L[i]].x)*(DG[L[i+1]].y+DG[L[i]].y)/2;
S:=abs(s);
writeln(f,V:0:2,' ',S:0:2);
For i:=1 to m do writeln(f,DG[L[i]].x,' ',DG[L[i]].y);
close(f);
end;
{=========================}
Begin
docDL;
xuat;
End.
VD2. Đa giác bao nhau
Cho N đa giác thoả mãn các tính chất
- Với 2 đa giác bất kỳ luôn 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.
Dagiac.INP
Dagiac.OUT
4
4 1 1 15 1 15 8 1 8
4 9 3 9 6 4 6 4 3
4 3 2 11 2 11 7 3 7
3 8 4 8 5 6 5
0
2
1
3
Bài toá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)
Dữ liệu vào: 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.
Dữ liệu ra: 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.
Ý tưởng:
- 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ỳ luôn 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
Chương trình:
Program dagiac;
var a,vt,kq: array[1..1000] of integer;
n,i:integer; fi,fo:text;
{=========================}
procedure doc_dl;
var i,j,min,k,x,y:integer;
begin
assign(fi,'dagiac.inp'); reset(fi);
readln(fi,n);
for i:=1 to n do
begin
read(fi,k); min:=maxint;
for j:=1 to k do
begin read(fi,x,y); if x<min then min:=x; end;
a[i]:=min;
vt[i]:=i;
end;
end;
{===========================}
procedure sapxep(l,r:integer);
var i,j,mid,tg:integer;
begin
i:=l; j:=r; mid:=a[(l+r) div 2];
repeat
while a[i]<mid do inc(i);
while mid<a[j] do dec(j);
if i<=j then
begin
tg:=a[i]; a[i]:=a[j]; a[j]:=tg;
tg:=vt[i]; vt[i]:=vt[j]; vt[j]:=tg;
i:=i+1; j:=j-1;
end;
until i>j;
if l<j then sapxep(l,j);
if i<r then sapxep(i,r);
end;
{===============================}
begin
doc_dl;
sapxep(1,n);
assign(fo,'Dagiac.out'); rewrite(fo);
for i:=1 to n do kq[vt[i]]:=i-1;
for i:=1 to n do writeln(fo,kq[i]);
close(fi); close(fo);
end.
VD3. Hình chữ nhật bao nhau
HCN.INP
HCN.OUT
6
1 5 2 2
2 4 3 3
1 5 5 2
4 3 8 1
5 6 8 4
6 6 8 5
2
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 (k1) 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.
Dữ liệu vào: Được cho trong tập tin HCN.INP
- Dòng thứ nhất ghi số N (1=N=1000).
- 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.
Kết quả: Đượ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.
Ý tưởng:
- 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 <HCN i bao HCN j > thì kq[i]:=kq[j]+1
Ch¬ng tr×nh:
Var x1,y1,x2,y2,kq:array[1..1000] of integer;
n: integer; fi,fo:text;
{===============================}
Procedure Doc_DL;
Var i:integer;
Begin
Assign(fi,'HCN.inp'); reset(fi);
readln(fi,n);
for i:=1 to n do read(fi,x1[i],y1[i],x2[i],y2[i]);
close(fi);
end;
{==================================}
Function DT_HCN(i:integer):longint;
Begin
DT_HCN:=longint(abs(x1[i]-x2[i]))*longint(abs(y1[i]-y2[i]));
end;
{=============================}
Procedure Qsort(l,r:integer);
Var i,j,mid,t:integer;
Begin
mid:=(l+r) div 2;
i:=l; j:=r;
Repeat
while DT_HCN(i)<DT_HCN(mid) do inc(i);
while DT_HCN(j)>DT_HCN(mid) do dec(j);
if i<=j then
begin
t:=x1[i]; x1[i]:=x1[j]; x1[j]:=t;
t:=x2[i]; x2[i]:=x2[j]; x2[j]:=t;
t:=y1[i]; y1[i]:=y1[j]; y1[j]:=t;
t:=y2[i]; y2[i]:=y2[j]; y2[j]:=t;
end;
until i>j;
if i<r then qsort(i,r);
if j>l then qsort(l,j);
end;
{===============================}
function Bao(i,j:integer):integer;
Begin
if (x1[i]<=x1[j]) and (y1[i]>=y1[j]) and (x2[i]>=x2[j])
and (y2[i]<=y2[j]) then bao:=1 else bao:=0;
end;
{==================================}
Procedure Xuly;
Var i,j:integer;
Begin
for i:=1 to n do kq[i]:=1;
for i:=2 to n do
for j:=1 to i-1 do
if bao(i,j)=1 then kq[i]:=kq[j]+1;
end;
{=================================}
BEGIN
doc_DL;
qsort(1,n);
xuly;
tmp:=0;
for i:=1 to n do
if kq[i]>tmp then tmp:=kq[i];
if tmp=1 then tmp:=-1;
assign(fo,'HCN.out'); rewrite(fo);
writeln(fo,tmp);
close(fo);
END.
VD4. Hình chữ nhật bao nhau
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.
HCN.IN
HCN.OUT
3
0 0 4 4
5 0 6 4
0 0 2 2
1 3
1 3
4
Dữ liệu vào: 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.
Kết quả: 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.
Ý tưởng:
- 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)
- Phương pháp tìm diện tích phủ đã trình bày ở dạng 3
Chương trình
const maxn=100;
Type Toa_do=record x1,y1,x2,y2:integer; end;
mang=array[1..2*maxn] of integer;
mang1=array[1..maxn,1..maxn] of integer;
var a:array[1..maxn] of toa_do;
x,y:mang; f,f1:text;
minx,miny,maxx,maxy,n:integer;
x1,y1,x2,y2:array[1..maxn] of integer;
kq:array[1..maxn,1..maxn] of byte;
s,bao:mang1;
{========================ar=========}
function min(a,b:integer):integer;
begin
if a>b then min:=b else min:=a;
end;
{================================}
function max(a,b:integer):integer;
begin
if a>b then max:=a else max:=b;
end;
{==================================}
procedure DocDL;
var i:integer;
Begin
assign(f,'HCN.IN'); reset(f);
readln(f,n);
for i:=1 to n do
begin
read(f,x1[i],y1[i],x2[i],y2[i]);
a[i].x1:=x1[i];a[i].y1:=y1[i];a[i].x2:=x2[i];a[i].y2:=y2[i];
if a[i].x1<minx then minx:=a[i].x1;
if a[i].x2<minx then minx:=a[i].x2;
if a[i].y1<miny then miny:=a[i].y1;
if a[i].y2<miny then miny:=a[i].y2;
if a[i].x1>maxx then maxx:=a[i].x1;
if a[i].x2>maxx then maxx:=a[i].x2;
if a[i].y1>maxy then maxy:=a[i].y1;
if a[i].y2>maxy then maxy:=a[i].y2;
end;
close(f);
end;
{========================================}
procedure Xuat(x,y:integer);
begin
if kq[x,y]=0 then write(f1,x,' ')
else xuat(x,kq[x,y]);
write(f1,y,' ');
end;
{=================================}
function DT(i:integer):integer;
begin
dt:=abs(x1[i]-x2[i])*abs(y1[i]-y2[i]);
end;
{=========================================}
function ktra_bao(i,j:integer):boolean;
begin
ktra_bao:=false;
if (min(x1[j],x2[j])>=min(x1[i],x2[i])) and
(min(y1[j],y2[j])>=min(y1[i],y2[i])) and
(max(x1[j],x2[j])<=max(x1[i],x2[i])) and
(max(y1[j],y2[j])<=max(y1[i],y2[i])) then ktra_bao:=true;
end;
{========================================}
procedure khoi_tao;
var i,j:integer;
Begin
for i:=1 to n do
for j:=1 to n do
if i<>j then
if ktra_bao(i,j) then Bao[i,j]:=1;
end;
{========================================}
procedure cau_a;
var i,j,k,io,jo:integer; fg:boolean;
begin
for i:=1 to n do
for j:=1 to n do
if i<>j then
for k:=1 to n do
if (i<>k) and (j<>k) and (Bao[i,k]+bao[k,j]>bao[i,j]) and
(bao[i,k]>0) and (bao[k,j]>0) then
begin
bao[i,j]:=bao[i,k]+bao[k,j];
kq[i,j]:=k;
end;
io:=1; jo:=2; fg:=true;
for i:=1 to n do
for j:=1 to n do
if bao[i,j]>bao[io,jo] then
begin io:=i; jo:=j; fg:=true; end
else if bao[i,j]=bao[io,jo] then fg:=false;
assign(f1,'HCN.out'); rewrite(f1);
if (bao[io,jo]>=1) and (fg=true) then xuat(io,jo)
else write(f1,'Khong');
end;
{====================================}
procedure cau_b;
var i,j,k,io,jo:integer; fg:boolean;
begin
writeln(f1);
fillchar(kq,sizeof(kq),0);
for i:=1 to n do
for j:=1 to n do
if (i<>j) and ktra_bao(i,j) then s[i,j]:=dt(i) + dt(j);
for i:=1 to n do
for j:=1 to n do
if i<>j then
for k:=1 to n do
if (i<>k) and (j<>k) and (s[i,k]+s[k,j]>s[i,j])
and (s[i,k]>0) and (s[k,j]>0) then
begin
s[i,j]:=s[i,k]+s[k,j];
kq[i,j]:=k;
end;
io:=1; jo:=2; fg:=true;
for i:=1 to n do
for j:=1 to n do
if (i<>j) and (s[i,j]>s[io,jo]) then
begin io:=i; jo:=j; fg:=true; end
else if s[i,j]=s[io,jo] then fg:=false;
if s[io,jo]>0 then xuat(io,jo) else writeln(f1,0);
end;
{====================================}
procedure cau_c;
var s1,i,j:integer;
{=================Sap xep mang tang dan=========}
Procedure sapxep(var t:mang);
var i,j,TG,m:integer;
begin
m:=2*n;
for i:=1 to m-1 do
for j:=i+1 to m do
if T[i]>T[j] then
begin
TG:=t[i];
T[i]:=T[j];
T[j]:=TG;
end;
end;
{========Kiem tra HCN moi thuoc HCN da cho===========}
function Kiemtra_Thuoc(i,j:integer):boolean;
var k:integer;
begin
kiemtra_thuoc:=true;
for k:=1 to n do
if (a[k].x1<=x[i-1]) and (x[i]<=a[k].x2)
and (a[k].y1<=y[j-1]) and (y[j]<=a[k].y2) then exit;
kiemtra_thuoc:=false;
end;
{*********************}
begin
s1:=0; docdl;
for i:=1 to n do
begin
X[i*2-1]:=a[i].x1;
X[2*i]:=a[i].x2;
Y[i*2-1]:=a[i].y1;
Y[2*i]:=a[i].y2;
end;
sapxep(X); sapxep(Y);
for i:=2 to 2*n do
for j:=2 to 2*n do
if kiemtra_thuoc(i,j) then s1:=s1+(x[i]-x[i-1])*(y[j]-y[j-1]);
writeln(f1);
writeln(f1,abs((maxx-minx)*(maxy-miny))-s1);
end;
{====================================}
begin
docDL;
khoi_tao;
cau_a;
cau_b;
cau_c;
close(f1);
end.
IV. BÀI TẬP ÁP DỤNG
Bài 1. Lớp đoạn thẳng
Cho tập n đoạn thẳng đánh số từ 1..n với các mút toạ độ là các số thực (Li,Ri), i:1..n trong đó Li, Ri lần lượt là các đầu mút bên trái và bên phải của đoạn thẳng thứ i.
Đoạn thẳng thứ i gọi là nằm trong đoạn thẳng thứ j nếu mọi điểm thuộc đoạn thẳng i đều thuộc đoạn thẳng j.
DL.INP
KQ.OUT
4
1 4
2 6
2 4
5 8
2
3 1 2 4
1 3
Người ta phân đoạn thẳng này thành từng lớp: Lớp của các đoạn thẳng là một tập hợp chứa các đoạn thẳng không nằm trong nhau.
Hãy phân lớp các đoạn thẳng trên sao cho số lớp là ít nhất.
Dữ liệu vào: DL.INP
- Dòng 1: Số n (n<=200)
- Dòng i+1 gồm 2 số nguyên lần lượt là Li, Ri.
Dữ liệu ra: KQ.Out
- Dòng 1: Số nguyên m là số lớp tìm được
- Mỗi dòng trong m dòng tiếp theo ghi thông tin mỗi lớp bao gồm số đoạn thẳng trong lớp tiếp theo là số hiệu của các đoạn thẳng thuộc lớp đó.
Ý tưởng:
- Sắp xếp các đoạn theo thứ tự tăng dần của độ dài
- Kiểm tra các đoạn bao nhau, sau đó lựa chọn các bộ chứa các đoạn thẳng không bao nhau
Ch¬ng tr×nh:
Program dagiac;
var a,vt,kq: array[1..1000] of integer;
n,i:integer; fi,fo:text;
{=========================}
procedure doc_dl;
var i,j,min,k,x,y:integer;
begin
assign(fi,'dagiac.inp'); reset(fi);
readln(fi,n);
for i:=1 to n do
begin
read(fi,k); min:=maxint;
for j:=1 to k do
begin read(fi,x,y); if x<min then min:=x; end;
a[i]:=min;
vt[i]:=i;
end;
end;
{===========================}
procedure sapxep(l,r:integer);
var i,j,mid,tg:integer;
begin
i:=l; j:=r; mid:=a[(l+r) div 2];
repeat
while a[i]<mid do inc(i);
while mid<a[j] do dec(j);
if i<=j then
begin
tg:=a[i]; a[i]:=a[j]; a[j]:=tg;
tg:=vt[i]; vt[i]:=vt[j]; vt[j]:=tg;
i:=i+1; j:=j-1;
end;
until i>j;
if l<j then sapxep(l,j);
if i<r then sapxep(i,r);
end;
{===============================}
begin
doc_dl;
sapxep(1,n);
assign(fo,'Dagiac.out'); rewrite(fo);
for i:=1 to n do kq[vt[i]]:=i-1;
for i:=1 to n do writeln(fo,kq[i]);
close(fi); close(fo);
end.
Bài 2. Xác định số điểm có toạ độ nguyên
Trong mặt phẳng toạ độ cho 3 điểm O, A, B trong đó O có toạ độ (0,0), A có toạ độ (x,y) là 2 số nguyên dương và B có toạ độ (z,0) với z là số nguyên dương. Viết chương trình đếm số điểm có toạ độ nguyên nằm bên trong tam giác OAB, không đếm các điểm trên cạnh.
DL.TXT
KQ.OUT
8 15 11
76
Dữ liệu vào: Từ tập tin DL.TXT gồm chứa 3 số x, y, z (0<x, y, z<100) các số cách nhau bởi một khoảng trắng.
Dữ liệu xuất: Tập tin văn bản KQ.out gồm một dòng chứa số các điểm có toạ độ nguyên nằm bên trong đa giác.
Ý tưởng:
- Đặt x1=0,y1=0,x2=x,y2=y,x3=z,y3=0
- Xác định số điểm có toạ độ nguyên nằm trong và trên biên đa giác:
a:=(x2-x1)*(y2+y1)+(x3-x2)*(y3+y2)+(x1-x3)*(y1+y3);
b:=UCLN(abs(x2-x1),abs(y2-y1))+UCLN(abs(x3-x2),abs(y3-y2))+UCLN(abs(x1-x3),abs(y1-y3));
sd:=round(abs(a/2)+b/2+1);
- Xác định số điểm có toạ độ nguyên nằm trên biên đa giác (kí hiệu là s)
- Số điểm có toạ độ nguyên nằm trong đa giác là: sd - s
Chương trình:
Program Dem_so_diem_nguyen;
Var N:longint; f:text;
x1,y1,x2,y2,x3,y3,x,y,z,a,b,sd:longint;
{================================}
procedure doc_dl;
begin
assign(f,'dagiac.inp'); reset(f);
n:=3;
readln(f,x,y,z);
x1:=0;y1:=0;x2:=x;y2:=y;x3:=z;y3:=0;
writeln(x1:3,y1:3,x2:3,y2:3,x3:3,y3:3);
end;
{================================}
Function UCLN(a,b:longint):longint;
var tg:longint;
begin
while b>0 do
begin tg:=b; b:=a mod b; a:=tg; end;
UCLN:=a;
end;
{==== kiem tra diem thuoc doan ===}
Function kiemtra(xa,ya,xb,yb,xo,yo:integer):boolean;
var f:real;maxx,maxy,minx,miny:integer;
begin
F:= (ya-yb)*xo+(xb-xa)*yo+(xa*yb-xb*ya);
if xa>xb then Maxx:=xa else Maxx:=xb;
if xa>xb then Minx:=xb else Minx:=xa;
if ya>yb then Maxy:=ya else Maxy:=yb;
if ya>yb then Miny:=yb else Miny:=ya;
if (F=0) and (minx<=xo) and (xo<=maxx) and (miny<=yo) and (yo<=maxy)
then kiemtra:=true else kiemtra:=false;
end;
{==Dem so diem nguyen nam tren cac canh==}
function dem:integer;
var s1,s2,max,min,i,j:integer;
begin
s1:=0; s2:=0;
if x2>x3 then begin max:=x2;min:=x3 end else begin max:=x3;min:=x2; end;
{===So diem nguyen tren OA===}
for i:=0 to x2 do
for j:=0 to y2 do
if kiemtra(0,0,x2,y2,i,j) then s1:=s1+1;
{===So diem nguyen tren AB===;so diem nguyen tren OB la z+1}
for i:=min to max do
for j:=0 to y2 do
if kiemtra(x2,y2,x3,0,i,j) then begin s2:=s2+1;writeln(i,' ',j);end;
dem:=s1+s2+(z+1)-3;
end;
{=================================}
BEGIN
doc_dl;
a:=(x2-x1)*(y2+y1)+(x3-x2)*(y3+y2)+(x1-x3)*(y1+y3);
b:=UCLN(abs(x2-x1),abs(y2-y1))+UCLN(abs(x3-x2),abs(y3-y2))+UCLN(abs(x1-x3),abs(y1-y3));
sd:=round(abs(a/2)+b/2+1);
writeln(sd-dem);
close(f);
readln;
END.
Bµi 3. Kho¶ng c¸ch xa nhÊt cña ®a gi¸c
Cho mét ®a gi¸c låi P cã n ®Ønh (n ≤ 50000), víi c¸c ®Ønh cã to¹ ®é nguyªn. h·y x¸c ®Þnh kho¶ng c¸ch gi÷a 2 ®iÓm xa nhau nhÊt thuéc ®a gi¸c låi P ®· cho.
Dacgiac.in
Dagiac.out
3
0 0
1 0
0 1
1.4142
D÷ liÖu vµo: D÷ liÖu vµo nhËp tõ file dagiac.in. Dßng ®Çu tiªn ghi sè n. N dßng tiÕp theo, mçi dßng ghi 2 sè x, y lµ to¹ ®é mét ®Ønh cña ®a gi¸c (-10000 ≤ x, y ≤ 10000). C¸c ®Ønh ghi theo chiÒu ngîc cña kim ®ång hå.
KÕt qu¶: KÕt qu¶ ghi ra c¸c file dagiac.out gåm 1 sè duy nhÊt lµ kho¶ng c¸ch cÇn t×m. KÕt qu¶ chÝnh x¸c ®Õn 4 ch÷ sè sau dÊu phÈy (hoÆc chÊm).
ý tëng:
- §êng th¼ng d ®îc gäi lµ ®êng th¼ng "®Æc biÖt" nÕu d cã ®iÓm chung víi ®a gi¸c P vµ toµn bé P n»m vÒ mét phÝa cña d
- Hai ®Ønh u vµ v cña ®a gi¸c P ®îc gäi lµ mét cÆp ″ch©n chèng″ nÕu qua chóng cã thÓ vÏ ®îc 2 ®êng th¼ng ″®Æc biÖt″ song song víi nhau.
- Kho¶ng c¸ch gi÷a 2 ®iÓm xa nhau nhÊt thuéc ®a gi¸c låi P lµ kho¶ng c¸ch gi÷a 2 ®êng ″®Æc biÖt″ xa nhau nhÊt.
Ch¬ng tr×nh:
var f:text;
m,n:integer;
x,y:array[1..5000] of integer;
kcmax:longint;
{===============================}
procedure doc_DL;
var i:integer;
begin
assign(f,'DL.INP'); reset(f);
readln(f,n);
for i:=1 to n do readln(f,x[i],y[i]);
close(f);
end;
{====================================}
function Next(i:integer):integer;
begin
if i<n then next:=i+1 else next:=1;
end;
{===================================}
function DT(i1,i2,i3:integer):longint;
begin
DT:=abs(longint((x[i2]-x[i1]))*(y[i2]+y[i1])
+longint((x[i3]-x[i2]))*(y[i3]+y[i2])
+longint((x[i1]-x[i3]))*(y[i3]+y[i1]));
end;
{=======================================}
function KC(i,j:integer):longint;
begin
kc:=sqr(longint(x[i]-x[j]))+sqr(longint(y[i]-y[j]));
end;
{======================================}
procedure xuly;
var a,p0,b,q0:integer;
begin
a:=n; b:=1; kcmax:=0;
while dt(a,next(a),next(b))>dt(a,next(a),b) do b:=next(b);
q0:=b;
while b<>1 do
begin
a:=next(a);
if kc(a,b)>kcmax then kcmax:=kc(a,b);
while dt(a,next(a),next(b))>dt(a,next(a),b) do
begin
b:=next(b);
if (a=q0) and (b=1) then exit
else if kc(a,b)>kcmax then kcmax:=kc(a,b);
end;
if dt(a,next(a),next(b))=dt(a,next(a),b) then
if (a<>0) or (b<>n) then
if kc(a,next(b))>kcmax then kcmax:=kc(a,next(b))
else if kc(next(a),b)>kcmax then kcmax:=kc(next(a),b);
end;
assign(f,'KQ.out'); rewrite(f);
writeln(f,sqrt(kcmax):0:4);
close(f);
end;
{===========================================}
Begin
Doc_DL;
xuly;
End.
Bµi 4. §o¹n th¼ng nh×n thÊy
Trªn mÆt ph¼ng to¹ ®é cho N ®o¹n th¼ng (1≤N≤100).To¹ ®é c¸c ®iÓm ®Çu, cuèi cña N ®o¹n th¼ng nµy lµ c¸c sè nguyªn kh«ng ©m nhá h¬n 20000. §êng th¼ng ®i qua mçi ®o¹n th¼ng nµy t¹o víi 2 trôc to¹ ®é nh÷ng tam gi¸c vu«ng c©n. Hai ®o¹n th¼ng bÊt k× trong N ®o¹n th¼ng nµy kh«ng cã ®iÓm chung.
Mét ®o¹n th¼ng ®îc gäi lµ nh×n thÊy ®îc tõ gèc to¹ ®é O(0,0), nÕu t×m ®îc 1 ®iÓm X trªn ®o¹n th¼ng sao cho ®o¹n th¼ng OX kh«ng cã ®iÓm chung víi bÊt cø ®o¹n th¼ng nµo trong c¸c ®o¹n th¼ng cßn l¹i.
Yªu cÇu: §Õm sè ®o¹n th¼ng nh×n thÊy ®îc tõ gèc to¹ ®é.
D÷ liÖu vµo tõ file LINE.INP cã:
LINE.INP
LINE.OUT
4
3 13 11 5
14 1 10 5
10 14 20 4
5 6 10 1
3
- Dßng ®Çu chøa sè nguyªn N (1≤N≤100) lµ sè lîng ®o¹n th¼ng
- Mçi dßng trong sè N dßng tiÕp theo chøa 4 sè X1, Y1, X2, Y2 c¸ch nhau bëi 1 kho¶ng tr¾ng. CÆp sè ®Çu biÓu diÔn to¹ ®é ®iÓm ®Çu, cÆp sè sau biÓu diÔn to¹ ®é ®iÓm cuèi cña ®o¹n th¼ng t¬ng øng.
KÕt qu¶ ghi ra tÖp LINE.OUT chøa mét dßng lµ sè lîng ®o¹n th¼ng nh×n thÊy ®îc.
ý tëng:
- S¾p xÕp c¸c ®o¹n th¼ng theo thø tù t¨ng dÇn cña kho¶ng c¸ch tõ O(0,0) ®Õn c¸c ®êng th¼ng ®ã. §ång thêi ®æi to¹ ®é ®iÓm ®Çu vµ ®iÓm cuèi cña mçi ®o¹n sao cho hoµnh ®é ®iÓm ®Çu kh«ng lín h¬n hoµnh ®é ®iÓm cuèi.
- §o¹n th¼ng thø nhÊt sau khi s¾p xÕp lu«n tho¶ m·n ®iÒu kiÖn bµi to¸n
- XÐt ®o¹n th¼ng thø i:
+ Gäi Q1,Q2 lÇn lît lµ to¹ ®é c¸c ®iÓm ®Çu mót cã hoµnh ®é nhá nhÊt vµ lín nhÊt trong sè c¸c ®iÓm ®Çu mót cña (i-1) ®o¹n th¼ng ®· xÐt tríc ®ã
+ Do ®êng th¼ng ®i qua mçi ®o¹n th¼ng t¹o víi 2 trôc to¹ ®é nh÷ng tam gi¸c vu«ng c©n vµ 2 ®o¹n th¼ng bÊt k× kh«ng cã ®iÓm chung nªn nÕu tia OQ1 hoÆc tia OQ2 c¾t ®o¹n th¼ng thø i th× ®o¹n th¼ng thø i ®îc xem lµ tho¶ m·n ®iÒu kiÖn bµi to¸n.
Ch¬ng tr×nh:
Program Bai4;
type diem =record x,y:integer; end;
doanthang=record dau,cuoi:diem; end;
heso=record a,b,c:real; end;
var a:array[1..100] of doanthang;
pt:array[1..100]of heso;
n,i,j,DEM:Integer; f:text;
{============}
procedure doc_dl;
var x1,y1,x2,y2:integer;
begin
assign(f,'line.inp');
reset(f);
readln(f,n);
for i:=1 to n do
begin
readln(f,x1,y1,x2,y2);
a[i].dau.x:=x1; a[i].dau.y:=y1;
a[i].cuoi.x:=x2; a[i].cuoi.y:=y2;
pt[i].a:=(y1-y2); pt[i].b:=(x2-x1) ; pt[i].c:=x1*y2-x2*y1;
end;
close(f);
end;
{=== khoang cach tu O den dt thu i ===}
Function kc(i:integer):real;
begin
kc:=abs(pt[i].c)/sqrt(sqr(pt[i].a)+sqr(pt[i].b));
end;
{=============}
procedure sapxep;
var i,j,tg1:integer; tg:doanthang;
begin
{== sap xep theo khoang cach tang dan tu O den cac duong thang=}
for i:=1 to n-1 do
for j:=i+1 to n do
if kc(i)>kc(j) then
begin
tg:=a[i]; a[i]:=a[j];a[j]:=tg;
end;
{==Dao toa do diem dau va diem cuoi sao cho dau.x<cuoi.x==}
for i:=1 to n do
if a[i].dau.x>a[i].cuoi.x then
begin
tg1:=a[i].dau.x;
a[i].dau.x:=a[i].cuoi.x;
a[i].cuoi.x:=tg1;
tg1:=a[i].dau.y;
a[i].dau.y:=a[i].cuoi.y;
a[i].cuoi.y:=tg1;
end;
end;
{=============}
Function Max(a,b:real):Real;
begin
if a>b then Max:=a else Max:=b;
end;
{=============}
Function Min(a,b:real):Real;
begin
if a>b then Min:=b else Min:=a;
end;
{===Kiem tra M thuoc doan ==}
Function Ktra(xo,yo,xa,ya,xb,yb:real):boolean;
begin
if (min(xa,xb)<=xo) and (xo<=max(xa,xb)) and (min(ya,yb)<=yo)
and (yo<=max(ya,yb))
then Ktra:=true else Ktra:=false;
end;
{===Kiem tra tia OA cat doan ===}
Function ktra2(P,Q,R,S:diem):boolean;
var a1,b1,c1,a2,b2,c2,D,Dx,Dy,xa,ya,xb,yb,xc,yc,xd,yd:integer;
begin
xa:=P.x;ya:=P.y;xb:=Q.x;yb:=Q.y;xc:=R.x;yc:=R.y;xd:=S.x;yd:=S.y;
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;
if (D<>0) and (ktra(Dx/D,Dy/D,xc,yc,xd,yd)) and ((Dx/D-xa)*(xb-xa)>=0) and ((Dy/D-ya)*(yb-ya)>=0)
then ktra2:=true else ktra2:=false;
end;
{==============}
procedure xuly;
var xmin,y1,xmax,y2:integer;Q1,Q2,P:diem;
begin
sapxep;
dem:=1; xmin:=a[1].dau.x; y1:=a[1].dau.y;
xmax:=a[1].cuoi.x;y2:=a[1].cuoi.y;
P.x:=0; P.y:=0;
for j:=2 to n do
begin
Q1.x:=xmin;Q1.y:=y1;
Q2.x:=xmax;Q2.y:=y2;
if ktra2(P,Q1,a[j].dau,a[j].cuoi)
or ktra2(P,Q2,a[j].dau,a[j].cuoi) then dem:=dem+1;
if a[j].dau.x< xmin then
begin xmin:=a[j].dau.x; y1:=a[j].dau.y;end;
if a[j].cuoi.x>xmax then
begin xmax:=a[j].cuoi.x;y2:=a[j].cuoi.y;end;
end;
end;
{==============}
Begin
doc_dl; xuly;
assign(f,'line.out'); rewrite(f); write(f,dem); close(f);
End.
Bµi 5. Chu vi
Cho N (0<N<200) h×nh ch÷ nhËt cã c¸c c¹nh song song víi c¸c trôc hoµnh vµ trôc tung cña hÖ trôc to¹ ®é vu«ng gãc. Mçi h×nh ch÷ nhËt cã thÓ bÞ che khuÊt mét phÇn hoÆc d¸n chång lªn mét h×nh ch÷ nhËt kh¸c. §é dµi ®êng biªn c¸c h×nh ch÷ nhËt ®îc gäi lµ chu vi c¸c h×nh ch÷ nhËt ®ã. ViÕt ch¬ng tr×nh tÝnh chu vi ®îc t¹o bëi c¸c h×nh ch÷ nhËt cho tríc.
§Ønh cña mçi h×nh ch÷ nhËt cã to¹ ®é nguyªn thuéc 0, 1000
D÷ liÖu vµo: Cho trong tËp tin v¨n b¶n HCN.INP
- Dßng ®Çu lµ sè nguyªn N.
- Dßng thø 2 ... N+1: Dßng i chøa to¹ ®é ®Ønh tr¸i díi vµ ®Ønh ph¶i trªn cña h×nh ch÷ nhËt i-1. To¹ ®é mçi ®Ønh ®îc cho bëi hoµnh ®é x, theo sau lµ tung ®é y.
HCN.INP
HCN.OUT
4
0 0 2 4
1 3 4 5
3 0 4 4
1 1 4 2
24
D÷ liÖu ra: Cho trong tËp tin v¨n b¶n HCN.OUT gåm mét sè nguyªn kh«ng ©m duy nhÊt lµ chu vi c¸c h×nh ch÷ nhËt cho trong tËp tin d÷ liÖu.
Ch¬ng tr×nh
const minlimit=0;
maxlimit=1000;
var v,sum:array[1..200] of integer;
x,y0,y1:array[1..2000] of integer;
d:array[1..2000] of shortint;
f:text; n, result:integer;
{=================================}
procedure Hieu_chinh(a:word; b,c:integer);
begin
if v[a]>0 then
sum[a]:=c-b+1
else
begin
sum[a]:=0;
if c>b then
sum[a]:=sum[a*2]+sum[a*2+1];
end;
end;
{=======================================}
procedure Sua_chua(node:word; node0, node1,a,b:integer; delta:shortint);
var tmp:integer;
begin
if (node0>=a) and (node1<=b) then v[node]:=v[node]+delta
else
begin
tmp:=(node0+node1) div 2;
if a<=tmp then Sua_chua(2*node,node0,tmp,a,b,delta);
if(tmp<b)and(tmp<node1)then sua_chua(2*node+1,tmp+1,node1,a,b,delta);
end;
Hieu_chinh(node,node0,node1);
end;
{========================================}
procedure DocDL1;
var a0,a1,b0,b1,i,k,min:integer;
begin
assign(f,'HCN.inp'); reset(f);
read(f,k);
n:=0; min:=0;
for i:=1 to k do
begin
read(f,a0,b0,a1,b1);
if b0<min then min:=b0;
if b1<min then min:=b1;
n:=n+1;
x[n]:=a0; y0[n]:=b0; y1[n]:=b1; d[n]:=1;
n:=n+1;
x[n]:=a1; y0[n]:=b0; y1[n]:=b1; d[n]:=-1;
end;
close(f);
if min<0 then
for i:=1 to n do
begin
y0[i]:=y0[i]-min; y1[i]:=y1[i]-min;
end;
end;
{=======================================}
procedure DocDL2;
var a0,a1,b0,b1,i,k,min:integer;
begin
assign(f,'HCN.inp'); reset(f);
read(f,k);
n:=0; min:=0;
for i:=1 to k do
begin
read(f,a0,b0,a1,b1);
if a0<min then min:=a0;
if a1<min then min:=a1;
n:=n+1;
x[n]:=b0; y0[n]:=a0; y1[n]:=a1; d[n]:=1;
n:=n+1;
x[n]:=b1; y0[n]:=a0; y1[n]:=a1; d[n]:=-1;
end;
close(f);
if min<0 then
for i:=1 to n do
begin
y0[i]:=y0[i]-min; y1[i]:=y1[i]-min;
end;
end;
{===========================================}
procedure sapxep;
var t,mx,md,i,j:integer; ts:shortint;
begin
for i:=1 to n-1 do
for j:=i+1 to n do
if x[i]>x[j] then
begin
t:=x[i]; x[i]:=x[j];x[j]:=t;
t:=y0[i]; y0[i]:=y0[j];y0[j]:=t;
t:=y1[i]; y1[i]:=y1[j];y1[j]:=t;
ts:=d[i]; d[i]:=d[j];
d[j]:=ts;
end;
end;
{========================================}
procedure xuly;
var tmp, i:integer;
begin
tmp:=0;
fillchar(sum,sizeof(sum),0);
fillchar(v,sizeof(v),0);
for i:=1 to n do
begin
result:=result+abs(tmp-sum[1]);
tmp:=sum[1];
Sua_chua(1,minlimit,maxlimit,y0[i],y1[i]-1,d[i]);
end;
result:=result+y1[n]-y0[n];
end;
{=====================================}
procedure xuatKQ;
begin
assign(f,'HCN.out'); rewrite(f);
writeln(f,result);
close(f);
end;
{=======================================}
BEGIN
result:=0;
DocDL1; sapxep; xuly;
DocDL2; sapxep; xuly;
XuatKQ;
END.
PAGE 22
Katyusha Le