Cong ty Cong Nghe Tin hoc Nha truong http://www.schoolnet.vn
PHƯƠNG PHÁP XÁC ĐỊNH ĐOẠN THẲNG NHÌN THẤY
07/08/2009

Bài toán: 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àotừ file LINE.INP có:

- 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 file 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,Q2lầ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ânvà 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 tham khảo:

Typediem =recordx,y:integer;end;

doanthang=recorddau,cuoi:diem;end;

heso=recorda,b,c:real;end;

var a:array[1..100] of doanthang;

pt:array[1..100]of heso;

n,i,j,DEM:Integer; f:text;

{============}

proceduredoc_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 ===}

Functionkc(i:integer):real;

begin

kc:=abs(pt[i].c)/sqrt(sqr(pt[i].a)+sqr(pt[i].b));

end;

{=============}

proceduresapxep;

vari,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

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;

{=============}

FunctionMax(a,b:real):Real;

begin

if a>b then Max:=a else Max:=b;

end;

{=============}

FunctionMin(a,b:real):Real;

begin

if a>b then Min:=b else Min:=a;

end;

{===Kiem tra M thuoc doan ==}

FunctionKtra(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 tratia OA cat doan ===}

Functionktra2(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)

thenktra2:=true else ktra2:=false;

end;

{==============}

procedurexuly;

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) thendem:=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.

Tác giả: Võ Sỹ Ngọc - GV Trường THPT Thành Sen, TP Hà Tĩnh
URL của bài viết này::http://www.schoolnet.vn/modules.php?name=News&file=article&sid=3425
© Cong ty Cong Nghe Tin hoc Nha truong contact: sales@schoolnet.vn