acm必做50題的解題-計(jì)算幾何

1、POJ 1113 WALL計(jì)算幾何，求凸包這題的結(jié)果等于這個(gè)多邊形步驟如下：的凸包的周長加上以所給半徑為半徑的圓的周長1)算法首先尋找最最靠下方的點(diǎn)，如果遇到 y 坐標(biāo)相同，則尋找x 坐標(biāo)最小的點(diǎn)P2)然后根據(jù)所有點(diǎn)相對(duì)于P 的偏角的大小進(jìn)行排序，遇到偏角相等的，只取距離P 最遠(yuǎn)的點(diǎn)(排序利用自己手寫的快排) 3)然后利用 Graham 算法求凸包4)最后直接求職#include #include#defin 3.1415926#define MAX_N 1000using namespatd;/原始輸入的坐標(biāo)值，rad 是輸入的半徑double cordMAX_N + 22, rad;seq

2、MAX_N + stackMAX_N n, top;P;realN; void swap(2;+ 2;1,2)temp = seq1;2;seqseq1 = seq2 = temp;dir(nodes,node1,node2)double double doublereturnx1x2 sx=cordnode10,cordnode20,cordnodes0,y1y2 sy=cordnode11;cordnode21;cordnodes1;(x2 - sx) * (y1 - sy) -(x1 - sx) * (y2 -sy);double getDist(node1,node2)doubledo

3、ublex1 =x2 =cordnode10,cordnode20,y1 = cordnode11;y2 = cordnode21;doublereturnres = sqrt(x1 - x2)res;* (x1 - x2) + (y1 - y2) * (y1 - y2);compare(node1,node2)double double doubledoublex1x2 sx=cordnode10, y1 = cordnode11;cordnode20, y2 = cordnode21;cord= dir(P0, sy = cordP, node1, node2);P1;typeif(typ

4、e =0)doubledoubledist1 =dist2 =(x1 - sx) *(x2 - sx) *(x1(x2-sx)sx)+(y1(y2-sy)sy)*(y1(y2-sy);sy);if(dist1 dist2) return -2;else if(dist1 = dist2)return0;elsereturn2;else if(type 0)return1;elsereturn-1;void fastSort(if(start start,end)end)cur= start; S = start,while(true)E =end +1;while(compare(seq+wh

5、ile(compare(seq-S,E,seqcurseqcur) 0 &S start);if(S swap(elsebreak;E)S,E);swap(cur,E);E - 1);1, end);fastSort(start,fastSort(E +void sortSeq()i, s = 0;for(i = 1; i = n; i+)/最低最左點(diǎn)不參加排序if(i =P)continue;seq+s = i;realN = n - 1; fastSort(1, realN);/夾角相同但是距離不同的點(diǎn)，只取舉例i = 1;while(i realN)P 最遠(yuǎn)的點(diǎn)s = i +/equal

6、 while(s1;angut smaller distance= realN & compare(seqi,seqs)=-2)seqs = -1; /置為無效s+;i = s;/尋找凸包 void findQ()nodes, node1, node2, type; top = 0;stacktop+ =P;s =c = while(c1;0; 2)if(seqs != -1)c+;stacktop+ = seqs; s+;for(; s =top-;elsebreak;0)stacktop+=seqs;doublegetRes()double totalDist lastNode = cur

7、Node;while(top 0)=0;P;curNode = stack-top;totalDist += getDist(lastNode,curNode);lastNode =curNode;/totalDist += totalDist += 2getDist(lastNode,* PI * rad;P);return totalDist;main()i; cinnrad;minX =_MAX, minY = for(i = 1; i cordi0cordi1;if(cordi1 minY) | (cordi1 =P = i;minX = cordi0;minY & cordi0 mi

8、nX)minY = cordi1;sortSeq(); findQ();double res = getRes();prf(%.0fn, res);return 0;POJ1292 Willna Jones Get There?題目大意：Jones 現(xiàn)在在位置 1，有人在位置 2 呼救，所以他要過去救他，但是有個(gè)條件，他必須在墻上走，其實(shí)就是說他只能在圖示的線段上走，但是線段間有空隙，所以要用一個(gè)長板搭板最小。段間才能從一個(gè)線段到另外一個(gè)線段，問怎么找到一個(gè)路徑使得要使用的長題目一眼看下去還比較復(fù)雜，畢竟你看到是一堆線段，但是這時(shí)候一個(gè)很直觀的就是枚舉兩個(gè)線段間的距離，將每個(gè)線段都看成是一個(gè)節(jié)

9、點(diǎn)，這樣其實(shí)就化為了一個(gè)簡單的有向圖，這時(shí)要尋找最短的長板其實(shí)最小生成樹的問題，利用 Prim 算法就可以解決，本題的難處就在于計(jì)算線段間的距離跟最小生成樹的實(shí)現(xiàn)。計(jì)算線段間距離寫得很亂，大家包容。#include#include #includefloat horDist(if ( x2 x1 )x1,y1,L1,x2,y2,L2 )if ( x2returnelsereturn x1+L1 )sqrt(float)(x2 - x1-L1)*(x2 - x1-L1)+(y2 - y1)*(y2 - y1);abs( y2 - y1 );elseif ( x1 x2 + L2)return s

10、qrt(float)(x1 - x2-L2)*(x1else- x2-L2)+(y2 - y1)*(y2 - y1);return abs(y2 - y1);float verDist(return horDist(x1,y1,L1,x2,y2,L2)y1, x1,-L1, y2, x2, -L2);float hor2verDist(x1,y1,L1,x2,y2,L2)xHor,yHor,LHor,0 )xVer,yVer,LVer;if ( L1xHor yHor LHor xVer yVer LVerelsexHor yHor LHor xVer yVer LVer=x1;y1;L1;x

11、2;y2;-L2;=x2;y2;L2;x1;y1;-L1;if( yVer= yHor&yHor = (yVer+LVer)if ( xHor = xVerreturn 0.0;else& xVer (xHor+LHor) )return xVer - xHor- LHor;elsereturn xHor - xVer;elseif ( xHor = xVer & xVer (yVer+ LVer) )return yHor - yVer - LVer;elsereturn yVer - yHor;elseif ( xVer (xHor+LHor) )if ( yHor (yVer+ LVer

12、) )return sqrt(float)( xHor - LHor), 2 );elsereturn sqrt(float)( LHor), 2 );else(float)(yHor- yVer- LVer),2)+(float)(xVer -(float)(yHor- yVer),2)+( (float)(xVer - xHor -if ( yHor (yVer+ LVer) )return sqrt(float)( xHor) , 2 );(float)(yHor - yVer - LVer),2)+( (float)(xVer -elsereturn sqrt(float)(2 );t

13、emplate(float)(yHor - yVer) ,2)+( (float)(xVer - xHor),T MinFloat( const T &a, const T&b )return (ab)?a:b;float dist(x1,y1,L1,x2,y2,L2 )if( L1 =0 )if ( L2returnelse if= 0 )sqrt(float)(float)(x1-x2),2)+(float)(y1-y2),2);( L2 0 )yTemp =xTemp =0;0;yTemp = xTemp = if ( y2returnelsereturny2-L2;x2;= y1 &

14、y1 = yTemp )abs( x1-x2 );MinFloat(sqrt(float)(float)(x1-x2),2)+(float)(y1-y2),2),sqrt(float)(elseyTemp xTemp(float)(x1-xTemp),2)+(float)(y1-yTemp),2);= 0;= 0;yTemp = y2;xTemp = x2+L2;if ( x2returnelsereturn= x1 & x1 = xTemp )abs( y1-y2 );MinFloat(sqrt(float)(float)(x1-x2),2)+(float)(y1-y2),2),sqrt(f

15、loat)(float)(x1-xTemp),2)+(float)(y1-yTemp),2);if( L2 = 0 )if ( L1= 0 )return sqrt(float)(float)(x1-x2),2)+(float)(y1-y2),2);else if ( L1yTemp = xTemp = 0 )0;0;yTemp = xTemp = if ( y1returnelsereturny1-L1;x1;= y2 & y2 = yTemp )abs( x1-x2 );MinFloat(sqrt(float)(float)(x1-x2),2)+(float)(y1-y2),2),sqrt

16、(float)(elseyTemp xTemp(float)(x2-xTemp),2)+(float)(y2-yTemp),2);= 0;= 0;yTemp = xTemp = if ( x1returnelsey1; x1+L1;= x2 & x2 0) 0)horDist( x1, y1, L1, x2, y2,L2);verDist( x1, y1, L1, x2, y2,L2);return hor2verDist( x1, y1, L1, x2, y2,L2);const const floatMaxValue = 1005;float MAXFLOAT = 10000000000.

17、0;DistArrayMaxValueMaxValue;struct WALLx;y; length;WALL walls MaxValue ; struct PoInfoparent; float path;bool bool;Pogoon;complete;Info info MaxValue;float Prim(i;while ( true )N )float minValue minIndex =for ( i = 0; i= MAXFLOAT;-1; N; +i )if ( info i .goon & !info i .complete )if ( infoi.path minV

18、alue )minValue = info i .path; minIndex = i;info minIndex .complete if ( minIndex = 1)break;for ( i = 0; i N; +i )if ( !info i .completeinfo i .goon = true; if (DistArray minIndex= true;& i!= minIndex) i info i.path)info i .path = DistArrayminIndex i ;info i .parent = minIndex;floength = 0.0; i = 1;

19、while( info i .parent != -1 )float temp = DistArray infoi.parent i ; if ( length temp )length = temp;i = info i .parent;return length;main()while( true )N;i;j; scanf(%d, &N ); if ( N = 0 )break;for ( i = 0; i N; +i )scanf(%d %d %d, &walls i .x,&walls i .y,&walls i .length);memset( DistArray, 0, size

20、of(DistArray) ); for ( i = 0; i N; +i )for ( j = i+1; j N; +j )DistArray i j = dist( walls i .x, wallsi.y,wallsi.length,walls j .x, walls j DistArray j ifor ( i = 1; i N;.y, walls j .length ); = DistArray i j ;+i )info info info infoinfo info info infofloi i ii.path = MAXFLOAT;.goon = false;.complet

21、e = false;.parent = 0;0000.path = 0;.goon = true;.complete = false;.parent = -1;ength = Prim( N );prf(%.2fn, length );return 0;poj2148Color the Map線段部分重合本題如果把圖建完了，其實(shí)就是枚舉總顏色數(shù)后 dfs 即可。所以本題的關(guān)鍵就是建圖啦。而建圖重要的是解決 Two countries are considered tobeadjacent if any of their territories sharea border of non-zero

22、length.亦即解決兩條線段部分重合的問題。解決部分重合的代碼如下：cross(const&ax,const&ay,const&bx,const&by)return ax*by-bx*ay;dot(const&ax,const&ay,const&bx,const&by)return ax*bx+ay*by;bool covered(const&pax,const&pay,const&pbx,const&pby,const&qax,const&qay,const&qbx,const&qby)if if(cross(pax-pbx,pay-pby,qax-qbx,qay-qby)!=0) ret

23、urn 0;(pax=qax&pay=qay&pbx=qbx&pby=qby)/prf(#1n);return 1;if(pax=qbx&pay=qby&pbx=qax&pby=qay)/prf(#2n);return 1;if(cross(pax-qax,pay-qay,pax-qbx,pay-qby)=0&dot(pax-qax,pay-qay,pax-qbx,pay-qby)0)/prf(#3n); return 1;if(cross(pbx-qax,pby-qay,pbx-qbx,pby-qby)=0&dot(pbx-qax,pby-qay,pbx-qbx,pby-qby)0)/prf

24、(#4n); return 1;if(cross(qax-pax,qay-pay,qax-pbx,qay-pby)=0&dot(qax-pax,qay-pay,qax-pbx,qay-pby)0)/prf(#3n); return 1;if(cross(qbx-pax,qby-pay,qbx-pbx,qby-pby)=0&dot(qbx-pax,qby-pay,qbx-pbx,qby-pby)0)/prf(#4n); return 1;return 0;POJ 2653 Pick-up sticks題目大意：給定一堆筷子，依次往下拋，給定筷子的兩斷點(diǎn)坐標(biāo)，求哪些筷子在最上面（即那些筷子上面沒有

25、其他筷子壓著）思路：判斷線段相交，用叉積。設(shè) p=(x1,y1),q=(x2,y2),則 pXq=x1*y2-x2*y1,若 pXq 為正數(shù)，則對(duì)于原點(diǎn)來說，p 在 q 的順時(shí)針方向上；若 pXq 為負(fù)數(shù)，則 p 在 q 的逆時(shí)針方向上。對(duì)于有公共斷點(diǎn)的三條線段來說，設(shè)該三條線段的向量分別為 p1,p2,p3,假設(shè) p2 在 p1 的逆時(shí)針方向上，p3 在 p1 的順時(shí)針方向上，那么(p2Xp1)*(p3Xp1)必定小于 0。#include #include #define EPS 1e-9 struct podouble x,y;struct Linepop1,p2;Line line10

26、0002; double MAX(double a,doubreturn ab?a:b;double MIN(double a,doubreturn ab?b:a;)double mulit(pop0,pop1,pop2)return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);cross(Line a,Line b) /判斷兩線段是否相交if(MAX(a.p1.x,a.p2.x)MIN(b.p1.x,b.p2.x)&MAX(b.p1.x,b.p2.x)MIN(a.p1.x,a.p2.x)&MAX(a.p1.y,a.p2.y)MIN(b.p1

27、.y,b.p2.y)&MAX(b.p1.y,b.p2.y)MIN(a.p1.y,a.p2.y)& mulit(a.p1,a.p2,b.p1)*mulit(a.p1,a.p2,b.p2)EPS& mulit(b.p1,b.p2,a.p1)*mulit(b.p1,b.p2,a.p2)EPS)return 1;return 0;main(void)n,i,j; while(1)scanf(%d,&n); if(n=0)break; for(i=1;i=n;i+)scanf(%lf %lf %lf %lf,&linei.p1.x,&linei.p1.y,&linei.p2.x,&linei.p2.y)

28、;prf(Top sticks:);for(i=1;i=n-1;i+)for(j=i+1;j=n;j+)if(cross(linei,linej) break;if(j=n) /若沒有其他筷子與其相交，則該筷子是最上面筷子之一prf( %d,i);prf( %d.n,n);return 0;POJ 1584 A Round Peg in a Ground Hole給你一個(gè)多邊形的 N 個(gè)頂點(diǎn)坐標(biāo)，然后再給一個(gè)釘子，給定釘子的半徑和圓心坐標(biāo)，首先判斷多邊形是否為凸多邊形，若為凸多邊形，再判斷釘子是否可以放到凸多邊形內(nèi)部。判斷是否為凸邊變形，第一步將頂點(diǎn)逆時(shí)針排列，再根據(jù) pipj 應(yīng)在 pi-1

29、pi 的逆時(shí)針方向，若存在 pipj 在 pi-1pj 的順時(shí)針方向，則該多邊形為凹多邊形。判斷圓(釘子)是否在多邊形內(nèi)部，第一步判斷圓心是否在凸多邊形內(nèi)部，第二步再判斷圓心到某一邊的最短距離，若存在某最短距離大于圓心，則圓不能放在凸多邊內(nèi)。#include #include #define eps 1e-8struct podouble x, y;pooperator-(pop)pores.x res.yres;= x - p.x;= y - p.y;return res;struct circlepoc;double r;double dis(pop1, pop2)pop3 =p2 - p

30、1;return sqrt(p3.x *p3.x + p3.y * p3.y);double multi(pop1,return p1.x * p2.ypop2)- p1.y * p2.x;void ChangeDir(pop,potmp;n)for(i = 0;i n / 2;i+)tmp = pi;pi = pn -pn - i - 1i=- 1;tmp;double AreaOfPloy(pop,n)double area= 0.0;0;i n;i+) multi(pi, pi/ 2;for(i =area +=return area+1);double AreaOfThree(pop1, poreturn fabs(multi(p2 - p1, p3p2,pop3)- p1) / 2;void OutPo(poq)prf(%.2lf%.2lf) , q.x,q.y);IsConvex(pop,n) /*判斷是否凸多邊形 */for(i = 1;i = n;i+)if(multi(pi % n - pi -return 1;1, p(i + 1) % n - pi % n) 0) return 0;IsInConvex(pop,n, poq) /* 點(diǎn)是否在凸多邊