算法合集之計(jì)算幾何學(xué)

1、發(fā)百稿計(jì)算幾何學(xué)是研究幾何問(wèn)題的算法，在現(xiàn)代工程學(xué)與數(shù)學(xué)，諸如計(jì)算機(jī)圖形學(xué)、計(jì)算機(jī)輔助設(shè)計(jì)、機(jī)器人學(xué)都要應(yīng)用計(jì)算幾何學(xué)，在信息學(xué)競(jìng)賽中幾何題也開(kāi)始出現(xiàn)了，但是在實(shí)際的競(jìng)賽中，幾何題得分率往往是最低的，所以我對(duì)幾何題的算法進(jìn)行了一下探索任何復(fù)雜的算法都是由許多簡(jiǎn)單的算法組合而成的，計(jì)算幾何題也同樣如此，先來(lái)看最基本的算法：1、求直線(xiàn)的斜率2、求2條直線(xiàn)的交點(diǎn)3、判斷2條線(xiàn)段是否相交4、求叉積等等。這些都是最基本的算法，是解幾何題的基礎(chǔ)，任何對(duì)基本算法的不熟悉，都可能導(dǎo)致解題的失敗，所以熟悉幾何題中的基本算法是非常重要的。但是有了基本算法是遠(yuǎn)遠(yuǎn)不夠的，因?yàn)楣饪扛?jìng)賽時(shí)的臨時(shí)思考，組合算法從時(shí)間上來(lái)說(shuō)

2、是來(lái)不及的，這就需要熟悉一些經(jīng)典算法，在競(jìng)賽中直接使用，比如：1、求凸包2、求最近點(diǎn)對(duì)3、判斷點(diǎn)是否在多邊形內(nèi)等等基本算法和經(jīng)典算法都是比較簡(jiǎn)單的，最后我們?cè)賮?lái)說(shuō)一下幾何題的題型及解幾何題的一些技巧,幾何題的幾種類(lèi)型1、 純粹的計(jì)算求解題解這一類(lèi)題除了需要有扎實(shí)的解析幾何的基礎(chǔ)，還要全面地看待問(wèn)題，仔細(xì)地分析題目中的特殊情況，比如求直線(xiàn)的斜率時(shí)，直線(xiàn)的斜率為無(wú)窮大，求2條直線(xiàn)的交點(diǎn)時(shí)，2直線(xiàn)平行，等等。這些都是要靠平時(shí)學(xué)習(xí)時(shí)的積累。2、 存在性問(wèn)題這一類(lèi)問(wèn)題可以用計(jì)算的方法來(lái)直接求解，如果求得了可行解，則說(shuō)明是存在的，否則就是不存在的，但是模型的效率同模型的抽象化程度有關(guān)，模型的抽象化程度越高

3、，它的效率也就越高，幾何模型的的抽象化程度是非常低的，而且存在性問(wèn)題一般在一個(gè)測(cè)試點(diǎn)上有好幾組測(cè)試數(shù)據(jù)，幾何模型的效率顯然是遠(yuǎn)遠(yuǎn)不能滿(mǎn)足要求的，這就需要對(duì)幾何模型進(jìn)行一定的變換，轉(zhuǎn)換成高效率的模型，下面就通過(guò)一個(gè)例子來(lái)對(duì)這種方法進(jìn)行一下闡述。3、 求幾何中的最佳值問(wèn)題這類(lèi)問(wèn)題是幾何題中比較難的問(wèn)題，一般沒(méi)有什么非常有效的算法能夠求得最佳解，最常用的是用近似算法去逼近最佳解，近似算法的優(yōu)劣也完全取決于得出的解與最優(yōu)解的近似程度。例1游戲者B在一張100*100紙上確定了一個(gè)目標(biāo)點(diǎn)，游戲者A一開(kāi)始在點(diǎn)（0,0）上，每次游戲者A從一個(gè)點(diǎn)到另一個(gè)點(diǎn)，如果新的點(diǎn)離目標(biāo)點(diǎn)近了，那么游戲者B說(shuō)“Hotter

4、”，如果新的點(diǎn)離目標(biāo)遠(yuǎn)了，那么游戲者B說(shuō)“Colder”，如果距離不變，那么游戲者B說(shuō)“Same'。輸入文件包括很多行，每行包含游戲者A這一步到達(dá)的點(diǎn)(x,y)和游戲者B說(shuō)的話(huà)，對(duì)每次游戲者B說(shuō)話(huà)，判斷目標(biāo)點(diǎn)可能的位置的面積，精確到小數(shù)點(diǎn)后2位。這是一道純粹的計(jì)算求解題，首先證明可能的位置的圖形一定是個(gè)凸多邊形。因?yàn)槊看螌?duì)游戲者B的回答，就可以確定可能的位置在出發(fā)點(diǎn)和到達(dá)點(diǎn)中垂線(xiàn)的哪一邊或就是中垂線(xiàn)，每次的可能圖形都是凸多邊形。所以這個(gè)圖形是許多個(gè)凸多邊形的交集，所以這個(gè)圖形是凸多邊形。接下來(lái)就是解題了，先令多邊形為一個(gè)四邊形，(0,0),(0,100),(100,100),(100,

5、0),然后對(duì)每次游戲者B的回答，用這條中垂線(xiàn)將多邊形分成2部分，取可能的那部分，即可。不過(guò)這樣并不是完全正確的，必須考慮到特殊情況，比如游戲者A到達(dá)的點(diǎn)和這步前的點(diǎn)完全相同，這時(shí)就不存在中垂線(xiàn)了，這些都是解題中要注意的重點(diǎn)。在這道題中就用到了很多解析集合的知識(shí)，包括求線(xiàn)段之間的交點(diǎn)，判斷點(diǎn)是否在線(xiàn)段的兩邊，證明最終圖形是凸多邊形等等。例2在一個(gè)無(wú)限長(zhǎng)的條形路上，有n(n<=200)個(gè)柱子，體積不計(jì),有一個(gè)人想從左邊走到右邊，人近似看成一個(gè)半徑為R的圓(如右圖)一問(wèn)能否實(shí)現(xiàn)。拿到這道題最基本的做法是對(duì)從最左邊的柱子到最右邊的柱子中，每一個(gè)豎列進(jìn)行掃描，計(jì)算可走到的范圍，如果到最右邊的柱子所

6、在的列都有可走到的范圍，則有解，否則無(wú)解?？墒侨绻钭蠛妥钣业?個(gè)柱子相距非常遠(yuǎn)，那么這樣計(jì)算的時(shí)間復(fù)雜度無(wú)疑是非常高的，所以我們應(yīng)該對(duì)這個(gè)幾何模型進(jìn)行轉(zhuǎn)化。首先在這個(gè)圖形中，不動(dòng)的是柱子（近似看成點(diǎn)），動(dòng)的是人（近似看成一個(gè)圓），這樣處理比較麻煩，所以我們應(yīng)該先把動(dòng)的轉(zhuǎn)換成點(diǎn)，圓轉(zhuǎn)換成圓心是最容易想到的，對(duì)圓心來(lái)說(shuō)，和柱子的距離不能<R,所以可以把每個(gè)柱子轉(zhuǎn)換為以其為圓心，半徑為R的圓，人轉(zhuǎn)換成他的圓心，這樣就使得計(jì)算可走到范圍容易多了。不過(guò)轉(zhuǎn)換成這個(gè)模型后，問(wèn)題還沒(méi)有得到根本的解決，必須進(jìn)一步的轉(zhuǎn)換。前2個(gè)算法有一個(gè)公共的特點(diǎn)，就是計(jì)算的都是圓外的部分，而計(jì)算圓內(nèi)的部分的連通性顯然比

7、計(jì)算圓外部分來(lái)得簡(jiǎn)單，所以我們現(xiàn)在的目標(biāo)就是把圓外部分換成圓內(nèi)部分。因?yàn)樽笥曳较蛏鲜菬o(wú)窮長(zhǎng)的，所以如果左右部分在圓外相通的話(huà)，那么上下兩條直線(xiàn)在圓內(nèi)部分就是不相通的，反之如果左右部分在圓外不相通的話(huà)，那么上下兩條直線(xiàn)在圓內(nèi)部分就是相通的，所以我們可以將對(duì)每一個(gè)豎列的掃描轉(zhuǎn)換成對(duì)每一個(gè)橫行的掃描，而且又是在圓內(nèi)操作，效率大大提高了。但是前面的轉(zhuǎn)換，對(duì)模型的抽象化程度卻一點(diǎn)也沒(méi)有改進(jìn)，如何在這方面進(jìn)行改進(jìn)無(wú)疑是最關(guān)鍵的。分析圓的特性，任意2個(gè)屬于同一個(gè)圓的點(diǎn)必定是相通的，這就啟發(fā)我們利用圓的特性，把難以處理的區(qū)域轉(zhuǎn)換成幾個(gè)具有代表性的點(diǎn)，使得能夠完全表示出區(qū)域連通的特性來(lái)，到了這里，應(yīng)該很容易就可

8、以看出，取每個(gè)圓的圓心是最好不過(guò)了，因?yàn)槊總€(gè)圓的大小完全相同，不存在包含，相切（如果內(nèi)切，就是重合了，如果外切，就是中間不連通的）等等復(fù)雜的關(guān)系，只有相交和相離的關(guān)系，而且如果2個(gè)圓之間相交的話(huà)，那么這2個(gè)圓就是相通的，可以在這2個(gè)圓的圓心之間連一條邊，增加一個(gè)源點(diǎn)，與上邊有交點(diǎn)的圓和源點(diǎn)連一條邊，增加一個(gè)匯點(diǎn)，與下邊有交點(diǎn)的圓和匯點(diǎn)連一條邊，這樣就把一道幾何題完全轉(zhuǎn)換成了一道圖論題，只要判斷源點(diǎn)和匯點(diǎn)之間是否有路就可以了，這是一道非常經(jīng)典的圖論題，解法就不說(shuō)了。從上面這道題的解題過(guò)程中，可以得出這樣的結(jié)論：解這一類(lèi)的幾何題必須充分了解幾何變換，挖掘題目中隱含的線(xiàn)索，對(duì)題目的本質(zhì)進(jìn)行充分的探索

9、，才能做好幾何題。例3一個(gè)農(nóng)夫在一個(gè)x*y的矩形田地上放牧n頭奶牛（n<=25）,它們互相之間都非常仇視，所以都希望能夠離其它奶牛盡量的遠(yuǎn)，它們有它們自己的標(biāo)準(zhǔn)，就是離其它奶牛的距離的倒數(shù)和越小越好，因?yàn)檗r(nóng)夫想讓它們盡量高興，所以他必須找到一種使所有的奶牛之間的距離的倒數(shù)和盡量小，不過(guò)學(xué)歷不高的農(nóng)夫覺(jué)得自己很難做到，請(qǐng)你來(lái)為他找到這種方案，他將按照方案的解和最優(yōu)解的差距來(lái)決定付給你的酬勞的多少（他知道最優(yōu)解還叫你求什么呢？；）輸入x,y,n,輸出你的解的n頭奶牛的位置。顯然這是一道求幾何最值的問(wèn)題，而且顯然是應(yīng)該用近似算法來(lái)做，那么決定解決問(wèn)題質(zhì)量的就是近似算法的優(yōu)劣。最簡(jiǎn)單的想法就是：

10、既然n最多也只不過(guò)是25,就來(lái)個(gè)“沒(méi)有功勞，也有苦勞”吧，對(duì)在正方形上手算得到的比較好的解，按照比例放到矩形里去，比如n=4時(shí)，正方形上的解是四個(gè)角，而一般（x,y之間相差不大）的矩形，這也就是最優(yōu)解了。但是這種算法在x,y之間差距比較大的時(shí)候，就充分顯示出它的不足了，和最優(yōu)解的差距非常大，幾乎1分也得不到了，所以這種算法并不是一種非常好的方法，只能夠混混而已。在求最優(yōu)解的題目中貪心法是很難有用武之地，但是貪心法是一種非常常用的近似算法，所以解這道題目，可以用貪心法一試。第一個(gè)點(diǎn)取（0,0）,以后每個(gè)點(diǎn)都取可以使當(dāng)前的倒數(shù)和最大的點(diǎn)，當(dāng)然這里要用到逐步求精法，這樣可以得到一個(gè)比較接近最優(yōu)解的方

11、案，經(jīng)過(guò)分析，也很難找到可以使貪心法得到離最優(yōu)解較遠(yuǎn)的數(shù)據(jù)，所以這道題中貪心法完全是一種有效的算法。不過(guò)貪心法終究和最優(yōu)解有一定距離，并不能得到所有的分?jǐn)?shù)，所以需要找到另一種更加有效的算法，由于這道題沒(méi)有固定的最佳解法，所以，對(duì)任何固定算法應(yīng)該都有使其得不到滿(mǎn)分的數(shù)據(jù)，所以我們又想到了非固定算法：隨機(jī)化算法。這個(gè)算法在這里我就不多介紹了，留給大家自己去思考：）附錄：程序題解第一題:programfat;constinputname='fat.in'outputname='fat.out'varf1,f2:text;x,y:array1.100ofreal;b:a

12、rray0.101,0.101ofboolean;i,j,k,n:integer;l,r:real;functiondis(x1,y1,x2,y2:real):real;求2點(diǎn)間距離的平方begindis:=sqr(x1-x2)+sqr(y1-y2);end;beginassign(f1,inputname);reset(f1);assign(f2,outputname);rewrite(f2);readln(f1,l,r);讀入輸入數(shù)據(jù)readln(f1,n);fori:=1tondoreadln(f1,xi,yi);fillchar(b,sizeof(b),false);轉(zhuǎn)換成圖論模型fo

13、ri:=1tondobeginifyi<=rthenbeginb0,i:=true;bi,0:=true;end;ifyi>=l-rthenbeginbi,n+1:=true;bn+1,i:=true;end;end;r:=4*r*r;fori:=1tondoforj:=i+1tondoifdis(xi,yi,xj,yj)<=rthenbeginbi,j:=true;bj,i:=true;end;fork:=0ton+1dofori:=0ton+1doforj:=0ton+1doifbi,kandbk,jthenbi,j:=true;求傳遞閉包ifb0,n+1thenwrit

14、eln(f2,'Notpossible')elsewriteln(f2,'Possible');close(f1);close(f2);end.第二題：programgame;constinputname='game.in'outputname='game.out'varf1,f2:text;i,j,t,f:integer;a:array1.100,1.2ofreal;d:array1.100ofinteger;xp,yp,x,y,xi1,xi2,xi3,zhi,x3,y3,x4,y4,sum:real;s:string;func

15、tionsq(x1,y1,x2,y2,x3,y3:real):real;求以(x1,y1),(x2,y2),(x3,y3)為頂點(diǎn)的三角形的面積beginsq:=abs(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2)/2;end;beginassign(f1,inputname);reset(f1);assign(f2,outputname);rewrite(f2);xp:=0;yp:=0;t:=4;初始化多邊形a1,1:=0;a1,2:=0;a2,1:=0;a2,2:=100;a3,1:=100;a3,2:=100;a4,1:=100;a4,2:=0;repeatre

16、ad(f1,x,y);readln(f1,s);whiles1=''dodelete(s,1,1);ifs='Same'thenbegint:=0;continue;end;if(x=xp)and(y=yp)thencontinue;考慮特殊情況：游戲者A沒(méi)有移動(dòng)i:=0;xi1:=2*(x-xp);xi2:=2*(y-yp);xi3:=xp*xp+yp*yp-x*x-y*y;求出中垂線(xiàn)的方程ifxi1*x+xi2*y+xi3>0thenf:=1elsef:=-1;ifs='Colder'thenf:=-f;fori:=1totdo判斷每個(gè)

17、點(diǎn)在中垂線(xiàn)的哪一側(cè)beginzhi:=xi1*ai,1+xi2*ai,2+xi3;ifzhi>0thendi:=1elseifzhi<0thendi:=-1elsedi:=0;end;at+1:=a1;dt+1:=d1;i:=1;whilei<=tdo增加多邊形和中垂線(xiàn)的交點(diǎn)beginifdi*di+1<0thenbeginforj:=t+1downtoi+1dobeginaj+1:=aj;dj+1:=dj;end;x3:=ai,1;y3:=ai,2;x4:=ai+2,1;y4:=ai+2,2;ifx3=x4thenbeginai+1,1:=x3;ai+1,2:=-(x

18、i3+xi1*ai+1,1)/xi2;endelsebeginai+1,1:=(x3*xi2*(y4-y3)-y3*xi2*(x4-x3)-xi3*(x4-x3)/(xi1*(x4-x3)+xi2*(y4-y3);ai+1,2:=(y4-y3)/(x4-x3)*(ai+1,1-x3)+y3;end;di+1:=0;inc(t);end;inc(i);end;i:=1;whilei<=tdo刪除不符合要求的點(diǎn)beginifdi=-fthenbeginforj:=i+1totdobeginaj-1：=aj；dj-1:=dj;end;dec(t);endelseinc(i);end;sum:=

19、0;fori:=2tot-1do求出多邊形的面積beginsum:=sum+sq(a1,1,a1,2,ai,1,ai,2,ai+1,1,ai+1,2);end;writeln(f2,sum:0:2);xp:=x;yp:=y;untileof(f1);close(f1);close(f2);end.第三題:貪心法programenemy;constinputname='enemy.in'outputname='enemy.out'varf1,f2:text;d:array1.25,1.2ofreal;i,j,k,l,x,y,n,bj,bk:integer;x1,y1,r,x2,y2,bs,sum,xz,yz:real;b1:boolean;functiondis(x1,y1,x2,y2:real):real;求(x1,y1),(x2,y2)間的距離begindis:=sqrt(sqr(x1-x2)+sqr(y1-y2);end;beginassign(f1,inputname);reset(f1);assign(f2,outputname);rewrite(f2);readln(f1,x,y,n);d1,1:=0;d1,2:=0;ifn>=2thenbe