PHNG PHP GII TON HNH HC BNG NGN NG LP TRNH PASCAL Ngy gi bi: 06/10/2010 S lt c: 354 Qua qu trnh

tham gia ging dy v bi dng hc sinh gii chng ti thy nhiu bi ton i hi hc sinh phi tm ra m hnh ton hc c th t yu cu phc tp ca bi ton. Thc t cho thy nhng hc sinh c kh nng vn dng kin thc ton hc vo qu trnh phn tch bi s nhanh chng pht hin c m hnh ton hc ca bi ton v a ra li gii hp l. Vic hng cho hc sinh pht hin ra nhng mi lin h ca bi ton cn gii quyt vi cc kin thc ton thng dng qua qu trnh tm hiu ni dung bi ton l khng d dng g. Vi mong mun phn no gip hc sinh cng nh gio vin trong vic tm ra li gii cho mt s dng bi ton thng gp trong chng trnh THPT cn gii quyt lp trnh l cc bi ton hnh hc, chng ti xin gii thiu phng php gii ton hnh hc bng ngn ng lp trnh Pascal m chng ti p dng trong qu trnh ging dy. I. KHI NIM HNH HC V CC I TNG HNH HC C BN 1. Khi nim hnh hc. a s cc thut ton u tp trung vo vn bn v cc con s, chng c thit k v x l sn trong phn ln cc mi trng lp trnh. i vi cc bi ton hnh hc th tnh hung khc hn, ngay c cc php ton s cp trn im v on thng cng c th l mt thch thc v tnh ton. Cc bi ton hnh hc th d hnh dung mt cch trc quan nhng chnh iu li c th l mt tr ngi. Nhiu bi ton c th gii quyt ngay lp tc bng cch nhn vo mt mnh giy nhng li i hi nhng chng trnh khng n gin. V d: Bi ton kim tra mt im c nm trong a gic hay khng? 2. i tng hnh hc c bn. Trong cc bi ton tin hc thuc loi hnh hc c 3 i tng c bn l: im, on thng v a gic. - im: c xc nh l cp (x,y) trong h to cc. - on thng: L cp im c ni vi nhau bng mt phn ca ng thng. - a gic: L dy cc im m 2 im lin tip ni vi nhau bi on thng v im u ni vi im cui to thnh ng gp khc khp kn. 3. D liu lu tr cc i tng hnh hc c bn

II. MT S PHP TON C BN 1. V tr tng i ca im so vi ng thng, tia v on thng Bi ton 1: Cho im . Yu cu:

a) Kim tra M c thuc ng thng i qua 2 im A, B hay khng? b) Kim tra M c thuc on thng AB hay khng c) Kim tra M c thuc tia AB hay khng Phng php: t - im M thuc ng thng AB khi - im M thuc on thng AB khi:

- Chng trnh: 2. Giao ca cc on thng, ng thng v tia Bi ton 2. Cho 2 ng thng c phng trnh (nu c) ca 2 ng thng trn. Phng php: . Tm giao im

+ Nu D=Dx=Dy=0 th kt lun 2 ng thng trng nhau + Nu D=0 v ((Dx 0) hoc (Dy 0)) th kt lun 2 ng thng song song + Nu D 0 th kt lun 2 ng thng ct nhau ti im c (Dx/D, Dy/D) Chng trnh: Bi ton 3. Cho 2 on thng AB v CD vi im (nu c) ca 2 on thng Phng php: Bc 1. Tm giao im M ca 2 ng thng AB v CD Bc 2. Kim tra M c thuc ng thi c 2 on AB v CD hay khng. Nu c l giao im cn tm, ngc li kt lun khng c. Chng trnh: Bi ton 4. Cho tia AM cha im B (khc A) v on thng CD vi . Tm giao im (nu c) ca tia AM vi on thng CD. - Phng php: Bc 1. Tm giao im N ca 2 ng thng AB v CD Bc 2. Kim tra N c thuc tia AM v on thng CD hay khng. Nu c l giao im cn tm, ngc li kt lun khng c. Chng trnh: 3. V tr ca im so vi a gic Bi ton 5. Cho a gic gm N nh min trong a gic. Phng php: Bc 1. Kim tra M c thuc cnh no ca a gic hay khng, nu c th kt lun M thuc min trong a gic v kt thc Bc 2. K MN song song vi trc honh (im N c honh ln hn max honh ca a gic) v im M. Xc nh v tr tng i ca M vi . Tm giao

Bc 3. Xc nh d l s giao im ca MN vi cc cnh ca a gic. Nhng trng hp sau c coi nh l tng thm 1 giao im: + nh d[i] khng thuc on thng MN, nh d[i+1] nm trn on thng MN, 2 nh d[i] v d[i+2] khc pha so vi ng thng MN. + nh d[i-1], d[i+2] ngoi on thng MN, hai nh d[i] v d[i+1] thuc on MN, d[i-1] v d[i+1] khc pha so vi ng thng MN + nh d[i] v d[i+1] khng thuc MN v cnh (d[i],d[i+1]) ct on thng MN V S Ngc (Cn tip) PHNG PHP GII TON HNH HC BNG NGN NG LP TRNH PASCAL (tip theo) Ngy gi bi: 15/10/2010 S lt c: 264 PHN II. MT S DNG BI TON HNH HC THNG GP Dng 1. Mi quan h gia im, on thng, a gic. Phng php: y l mt trong s dng bi ton hnh hc n gin nht. Vic gii bi ton dng ny ch yu s dng cc kin thc hnh hc c bn ( trnh by y trong phn trn) VD1 Ba im thng hng Cho N im, hy kim tra xem c bao nhiu b 3 im thng hng. Input: Cho trong tp vn bn DL.INP - Dng th 1 ghi s N - N dng tip theo, mi dng ghi to ca mt im. Output: Ghi vo tp KQ.OUT cha mt s duy nht l s b 3 im thng hng.

(Gii hn: 1<=N<=2000, to cc im c gi tr tuyt i khng qu 10000)

Chng trnh:

VD2. ng thng ct nhau Cho n ng thng AiBi (1 i n) phn bit vi Ai, Bi l cc im cho trc. Hy thng bo ra mn hnh cc cp ng thng i mt ct nhau. D liu: Cho trong file DL.INP gm N dng (N khng bit trc). Dng th i ghi 4 s thc xAi yAi xBi yBi. Cc s trn cng mt dng ghi cch nhau t nht mt du cch.

 tng: - Mi ng thng c c trng bi 3 thng s a,b,c c xc nh:

- Hai ng thng ct nhau khi: D:=a1*b2-a2*b1 ? 0; Chng trnh:

VD3. im thuc a gic. Cho a gic khng t ct A1A2...AN vi cc nh Ai(xi,yi) nguyn. Vi im A(xA,yA) cho trc, hy xc nh xem A c nm trong a gic cho hay khng (Trong trng hp trn cnh a gic xem nh nm trong a gic)

D liu: Cho trong tp Dagiac.inp + Dng u l s N + N dng tip theo mi dng ghi xi,yi l to Ai + Dng n+2 ghi 2 s xA v yA D liu l cc s nguyn.

Kt qu: a ra mn hnh thng bo im A c nm trong a gic hay khng tng: - Lu to cc nh a gic vo mng A - Kim tra xem im A c trng vi nh a gic - Kim tra xem im A c nm trn cnh a gic - Tm giao im nu c ca tia Ax (Ax//Ox v Ax hng theo phn dng trc honh) vi cc cnh ca a gic. Trng hp tia Ax cha on thng cnh a gic ta xem nh tia Ax c 1 im chung vi cnh ny. C th: + Gi s im A(x0,y0), chn im B(xb,yb) vi xb=x0+1,yb=y0 + Kim tra tia AB c ct on thng CD bng cch: B1. Tm giao im N ca 2 ng thng AB v CD Tnh
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;

Xc nh: Nu D 0 th to giao im l N(Dx/D,Dy/D) B2. Kim tra N c thuc tia AM v on thng CD hay khng. - im N thuc on thng CD khi: Min(xC,xD) xN Max(xC,xD) v Min(yC,yD) yN Max(yC,yD) - im N thuc tia AB khi (yN-yA)(yB-yA) 0 c ngha l N phi tho mn iu kin: (xN-xA)(xB-xA) 0 v

+ Kim tra tia AB cha cnh CD hay khng bng cch: (yc=yd)and(yc=yo) - m s giao im, nu s giao im l th A thuc a gic Chng trnh:

VD4. m s im c to nguyn thuc a gic Cho a gic gm n nh (x1,y1), (x2,y2), ..., (xn,yn), bit (2<104), x v yi(i=1,...,n) l cc s nguyn trong on [-106,106]. Cc nh c lit k theo th t cng chiu kim ng h. Vit chng trnh tm s im c to nguyn nm trong hay trn bin a gic.

D liu: Cho trong tp tin DL.INP. - Dng u cha s nguyn duy nht cho bit s nh. - Tip theo l cc dng, trn mi dng c 2 s nguyn cch nhau mt khong trng ln lt l honh , tung cc nh a gic. Kt qu: Xut ra mn hnh s im c to nguyn nm trong hay trn bin a gic tng: - Tnh a,b theo cng thc:

- Xc nh s im c to nguyn: S=round(abs(a/2)+b/2+1) Chng trnh:

Dng 2.Tnh din tch a gic Phng php: Gi s cho a gic c n nh v to cc nh lu vo mng a. tnh din tch a gic ta lm nh sau: Bc 1. Gn thm nh ph:
a[n+1].x:=a[1].x; a[n+1].y:=a[1].y;

Bc 2. Din tch a gic tnh theo cng thc:

Lu : C th p dng cng thc khc tnh din tch trong cc trng hp c bit. - Nu a gic l tam gic (n=3) th din tch tnh theo cng thc:

- Nu a gic l hnh ch nht (n=4) c cc cnh l a,b th din tch l: S=ab - Nu a gic l hnh vung (n=4) c cnh l a th din tch l: S=a2 - Nu a gic l hnh trn c bn knh R th din tch l VD1. Xc nh din tch a gic Cho N a gic li A1A2A3...AN-1AN vi cc nh Ai(xi,yi) c to nguyn. Hy tnh din tch a gic trn.

D liu: Cho trong file DL.INP gm 2 dng - Dng 1: Cha s nguyn dng N - Dng 2: Cha 2xN s nguyn dng x1 y1 x2 y2...xN yN l to cc nh ca a gic. Mi s ghi cch nhau mt du cch. Kt qu: Xut ra mn hnh din tch a gic. tng: - Lu to cc nh a gic vo mng toado - S dng cng thc tnh din tch a gic:

VD2. Dy hnh ch nht Trong mt phng to trc chun, cho N hnh ch nht c cc cnh song song vi trc to . Mi HCN c xc nh bi to nh di bn tri v nh trn bn phi ca n. Hy a ra dy cc hnh ch nht theo th t tng dn din tch . D liu: Cho trong file HCN.inp gm N+1 dng. - Dng 1. Cha s N -Dng i+1 (1 i N): Ghi 4 s nguyn x1, y1, x2 ,y2 ln lt l to nh di bn tri v nh trn bn phi ca HCN i. (Cc s ghi trn mt dng cch nhau t nht mt du cch)

Kt qu: Ghi vo tp HCN.out dy cc hnh ch nht sau khi sp xp.

 tng: - Lu to cc nh a gic vo mng a - Tnh din tch hnh ch nht theo cng thc:

- Sp xp mng a tng dn theo din tch tng:

Cn na

PHNG PHP GII TON HNH HC BNG NGN NG LP TRNH PASCAL (tip theo) Ngy gi bi: 22/10/2010 S lt c: 251 PHN II. MT S DNG BI TON HNH HC THNG GP Dng 3. Xc nh din tch ph bi cc hnh ch nht Phng php: Gi s c n hnh ch nht. tnh din tch ph bi n hnh ch nht ta lm nh sau: Bc 1. S dng a,b ln lt l cc mng lu honh v tung cc nh hnh ch nht (mi hnh ch nht ch cn lu to 2 nh i din qua tm hnh ch nht). Bc 2. Sp xp mng a,b theo th t tng dn Bc 3. Ln lt kim tra cc hnh ch nht c to nh trn bn phi (xi+1,yi+1) v to nh di bn phi l (xi,yi) vi 1 i n-1. Nu hnh ch nht ny thuc mt trong cc hnh ch nht ban u th cng thm vo phn din tch ang cn tm din tch ca hnh ch nht con ny. V d 1. Din tch ph bi cc hnh ch nht Trong mt phng to trc chun, cho N hnh ch nht c cc cnh song song vi trc to . Mi HCN c xc nh bi to nh di bn tri v nh trn bn phi ca n. Hy tnh din tch phn mt phng b ph bi cc HCN trn. D liu: Cho trong file HCN.inp gm N+1 dng. - Dng 1: Cha s N -Dng i+1 (1 i N): Ghi 4 s nguyn x1,y1,x2,y2 ln lt l to nh di bn tri v nh trn bn phi ca HCN i. Cc s ghi trn mt dng cch nhau t nht mt du cch. Kt qu: a ra mn hnh din tch phn mt phng b ph bi hnh ch nht trn. tng: - Lp mng X[1..2n], Y[1..2n] ln lt cha honh , tung cc hnh ch nht - Lu to ban u cc hnh ch nht vo mng a - Sp xp mng X,Y tng dn

- Ln lt kim tra cc hnh ch nht c to nh trn bn phi (xi+1,yi+1) v to nh di bn phi l (xi,yi) vi 1 i n-1. Nu hnh ch nht ny thuc mt trong cc hnh ch nht ban u th cng thm vo phn din tch ang cn tm din tch ca hnh ch nht con ny. Chng trnh:

V d 2.Ph S Trn mt phng ta , mt hnh ch nht vi cc cnh song song vi cc trc to c xc nh bi hai im i tm: nh gc trn bn tri v nh gc di bn phi. Cho N hnh ch nht song song vi cc trc to . Ph S ca cc hnh ch nht c din tch nh nht cha N hnh ch nht cho. D liu vo: c t tp PHUCN.INP c cu trc: - Dng u tin cha N (N 30); - Trong N dng tip theo, mi dng ghi 4 s l to ca hai nh i tm ca mt hnh ch nht, cc s ny l cc s nguyn c tr tuyt i khng qu 100. Kt qu: Ghi ra tp vn bn PHUCN.OUT - Dng 1 ghi to hai nh i tm ca ph S cc hnh ch nht - Dng 2 ghi din tch ca phn hnh S khng nm trong hnh ch nht no trong N hnh cho - tng: - Xc nh hnh ch nht H nh nht bao tt c cc hnh ch nht ban u: Gi minx,maxx ln lt l honh nh nht v ln nht trong cc honh cc nh hnh ch nht cho; miny, maxy ln lt l tung nh nht v ln nht trong cc tung cc nh hnh ch nht cho. Khi hnh H c to nh di tri l (minx,miny) v nh trn phi l (max,maxy). l ph S cn tm. - Tnh din tch hnh H l (maxx-minx)(maxy-miny) - Tnh din tch s ph bi cc hnh ch nht ( nu r phng php chung) - Phn din tch cn tm l: s1:=abs((maxx-minx)*(maxy-miny))-s - Chng trnh:

V d 3. Din tch ph bi cc hnh trn Trn mt phng cho N hnh trn. Tnh din tch phn mt phng b ph bi cc hnh trn trn. D liu: Cho trong file INP.BL3 dng u l s lng hnh trn, t dng th 2 tr i mi dng cha 3 s nguyn dng l ta x, y ca tm v bn knh ca tng hnh trn (cc s trn cng mt dng ghi cch nhau t nht 1 du cch) Kt qu: Xut ra mn hnh - tng: - Tm hnh ch nht nh nht c cc cnh song song vi cc trc to v cha ton b N hnh trn - Chia hnh ch nht ny thnh li cc vung c cnh 0.1 n v, vi mi thuc hnh ch nht kim tra xem ny c thuc vo hnh trn no hay khng, nu c th tng din tch cn tnh ln 0.01 n v. - Chng trnh

Dng 4. Xc nh a gic nh nht bao tt c cc im, a gic cho Phng php: Cho N im A1, A2, ..., AN trn mt phng. xc nh mt a gic khng t ct cha mt s im cho v bao tt c cc im cn li ta lm nh sau: Bc 1. Tm im c tung nh nht. im s l nh a gic

Bc 2. Gi s ta chn c im PM. Tm im Pi sao cho gc hp bi PMPi v trc honh l nh nht v ng thi gc ny phi ln hn gc hp bi PMPM-1 v trc honh. im Pi s l mt nh ca a gic. Bc 3. Ly kt qu l dy cc nh P tm c. Lu : Vi bi ton tm a gic bao nhau th cn ghi nh a gic a bao a gic b khi mi im trong a gic b u nm trong a gic a. V d 1. a gic khng t ct Cho N im A1, A2, ..., AN trn mt phng. Cc im u c to nguyn v khng c 3 im bt k trong chng thng hng. Hy vit chng trnh thc hin cc cng vic sau y: Xc nh mt a gic khng t ct c nh l mt s im trong cc im cho v cha tt c cc im cn li v c chu vi nh nht. Hy tnh din tch a gic ny. D liu: cho trong tp HCN.INP gm n+1 dng + Dng 1: Cha s N + Dng i+1 (1 i N): Ghi 2 ch s nguyn xi,yi l to nh Ai. Cc s trn cng mt dng cch nhau mt khong trng. Kt qu: Xut ra tp HCN.Out + Dng 1: Ghi 3 s K, V, S vi K l s nh a gic tm c, V l chu vi, S l din tch ca n. + Dng i+1(1 i K): Ghi to ca nh a gic. - tng: - Tm im c tung nh nht. im s l nh a gic - Gi s ta chn c im PM. Tm im Pi sao cho gc hp bi PMPi v trc honh l nh nht v ng thi gc ny phi ln hn gc hp bi PMPM-1 v trc honh. im Pi s l mt nh ca a gic.

V d 2. a gic bao nhau Cho N a gic tho mn cc tnh cht - Vi 2 a gic bt k lun c mt a gic m mi im ca n nm trong a gic kia. - Cc cnh ca chng khng c im chung. Bi ton t ra l: Vi mi a gic i, c bao nhiu a gic bao n? (i nm trong bao nhiu a gic) D liu vo: Ghi trong tp tin vn bn Dagiac.Inp. - Dng u tin ghi s t nhin N (3N10000). - Trn N dng tip theo: Dng th i+1 ghi thng tin v a gic c s hiu th i. Bao gm s u tin Si l s nh ca a gic (Si3), Si cp s nguyn tip theo ln lt l honh v tung cc nh ca a gic. Cc s trn cng dng cch nhau bi t nht mt khong trng. D liu ra: Ghi trong tp tin Dagiac.Out - Gm N dng - Dng th i: Ghi s lng a gic bao a gic i. - tng: - S dng cc mng a,vt,kq (vi a[i] lu gi tr honh nh nht ca cc nh ca a gic th i, vt[i] ch a gic th i, mng kq lu kt qu) - Thc hin sp xp cc a gic theo th t tng dn ca gi tr honh nh nht ca cc nh ca cc a gic. - Do theo iu kin bi ton l vi 2 a gic bt k lun c mt a gic m mi im ca n nm trong a gic kia nn KQ[vt[i]] =i-1 - Chng trnh:

V d 3. Hnh ch nht bao nhau Cho N hnh ch nht trn mt phng m cc cnh song song vi cc trc to . Bit hnh ch nht i bao hnh ch nht j nu c 4 nh ca hnh ch nht j u nm trong hnh ch nht i hoc nm trn cnh ca hnh ch nht i. Mt dy cc hnh ch nht c gi l hnh ch nht bao nhau chiu di k (k1) nu dy ny gm cc hnh ch nht H1, H2, ..., Hk sao cho hnh ch nht i bao hnh ch nht i+1 vi i=1 ... (k-1). Hy tm s k ln nht ni trn.

D liu vo: c cho trong tp tin HCN.INP - Dng th nht ghi s N (1N1000). - N dng tip theo, dng th i ghi 4 s nguyn x1, y1, x2, y2 (10000< x1,y1,x2,y2<10000) ln lt l honh , tung cc nh tri trn, phi di ca hnh ch nht. Kt qu: c ghi vo tp vn bn HCN.OUT gm mt dng cha s nguyn duy nht l s k tm c hoc s -1 nu khng tn ti s k tho iu kin bi. - tng: - Tnh din tch cc hnh ch nht (HCN) - Sp xp li cc HCN theo th t khng gim ca din tch cc HCN - Lp hm kim tra HCN i bao HCN j, tho mn iu kin: (x1[i]<=x1[j]) and (y1[i]>=y1[j]) and (x2[i]>=x2[j]) and (y2[i]<=y2[j]) - Xc nh s lng cc HCN bao HCN i v lu vo phn t mng kq[i] bit rng: nu th kq[i]:=kq[j]+1 - Chng trnh:

V d 4. Hnh ch nht bao nhau Hnh ch nht A bao hnh ch nht B nu mi im thuc hnh ch nht B u nm trong hoc thuc hnh ch nht A. Trong mt phng Oxy cho n hnh ch nht c cc cch song song vi cc trc to . Yu cu: 1. Tm s hnh ch nht bao nhau nhiu nht (s lng hnh phi >1). 2. Trong s cc tp hnh ch nht bao nhau, tm tp cc hnh ch nht bao nhau c tng din cc din tch ca cc hnh ch nht trong tp l ln nht. 3. Tm hiu din tch ca hnh ch nht nh nht bao tt c cc hnh ch nht cho vi din tch ca phn mt phng b ph bi cc hnh ch nht cho. D liu vo: Cho trong tp vn bn HCN.IN - Dng u: n (s lng hnh ch nht, 1N1000) - n dng tip theo: Mi dng cha 4 s dng a, b, c, d (a, b, c, d l cc s nguyn) vi (a, b) v (c, d) l to ca hai nh i tm ca hnh ch nht. Kt qu: Xut ra tp vn bn HCN.Out - Dng u: Cho bit tp cc hnh ch nht bao nhau nhiu nht theo dng k l m n ... vi nghaHnh ch nht th k thuc hnh ch nht th l, hnh ch nht th l thuc hnh ch nht th m, hnh ch nht th m thuc hnh ch nht n ... nu khng c th ghi t "khong" - Dng th 2: Cho bit tp cc hnh ch nht bao nhau c tng cc din tch ca cc hnh ch nht trong tp hp l ln nht theo qui cch nh dng th nht. Nu khng th ghi s 0. - Dng th 3: Cha con s biu din hiu din tch hnh ch nht nh nht bao tt c hnh ch nht cho vi din tch ca phn mt phng b ph bi cc hnh ch nht cho. - tng: - Lu ta cc nh hnh ch nht vo 4 mng x1,y1,x2,y2 - Dng mng bao(n,n) nh du cc hnh ch nht bao nhau: Vi bao[i,j]=1 c ngha hnh ch nht i bao hnh ch nht j, bao[i,j]=0 th ngc li. - Dy hnh ch nht th i, k, j gi l bao nhau nu (Bao[i,k]+bao[k,j]>bao[i,j]) v (bao[i,k]>0) v (bao[k,j]>0). S dng mng KQ lu cc hnh ch nht k tho mn

- Hnh ch nht nh nht bao tt c cc hnh ch nht cho l hnh ch nht c to gc di phi l (xmin,ymin) v to gc trn tri l (xmax,ymax) - Phng php tm din tch ph trnh by dng 3 Chng trnh

Cn na