学步园

很长一段时间没有写总结了，随着冬令营的结束，最近对大幅度的总结。

最后一天LRJ讲了下计算几何我才发现3D凸包原来如此简单。

主要讲了两个算法：包裹法和增量算法。

个人感觉增量法比较好，整个过程只用到了+-*这集中运算，不涉及实数运算。

包裹法：首先确定一条一定为凸包上的线段，然后由这条线段为轴，像包纸一样的往顺时针（逆时针）包，碰到的第一个点就是凸包上的点，这时候又可以确定两条直线，递归操作；

增量法：首先任选4个点形成的一个四面体，然后每次新加一个点；

            分两种情况：1.在凸包内，无视；

                              2.在凸包外，找到从这个点可以“看见”的面，删除这些面，然后对于一边没有面的线段，和新加的这个点新建一个面；

            至于这个点可以看见的面，就是求出这个面的方程（可以直接求法向量）。

明天就是冬令营了，{$RP++}！

code：

program poj3528;<br /> type<br /> point=record x,y,z:real end;<br /> mian=record<br /> v:array[1..4] of longint;<br /> f:point;c:real;<br /> end;<br /> var<br /> p:array[0..500] of point;<br /> s:array[0..2000] of mian;<br /> o:array[0..2000] of boolean;<br /> fa:array[0..2000] of longint;<br /> e:array[0..500,0..500] of longint;<br /> i,j,k,t,n,pt:longint;<br /> u:point;ans:real;<br /> function next(i:longint):longint;<br /> begin if fa[i]<>i then fa[i]:=next(fa[i]);next:=fa[i] end;<br /> operator -(a,b:point)c:point;<br /> begin c.x:=a.x-b.x;c.y:=a.y-b.y;c.z:=a.z-b.z end;<br /> operator +(a,b:point)c:real;<br /> begin c:=a.x*b.x+a.y*b.y+a.z*b.z end;<br /> operator *(a,b:point)c:point;<br /> begin<br /> c.z:=a.x*b.y-a.y*b.x;<br /> c.x:=a.y*b.z-a.z*b.y;<br /> c.y:=a.z*b.x-a.x*b.z;<br /> end;<br /> procedure new(i,j,k:longint);var l:longint;<br /> begin<br /> inc(t);fa[t+1]:=t+1;<br /> with s[t] do begin<br /> v[1]:=i;v[2]:=j;<br /> v[3]:=k;v[4]:=i;<br /> f:=(p[j]-p[i])*(p[k]-p[i]);<br /> c:=f+p[i];<br /> for l:=1 to 3 do e[v[l],v[l+1]]:=t;<br /> end;<br /> end;<br /> procedure init(i,j,k,l:longint);var f:point;<br /> begin<br /> f:=(p[j]-p[i])*(p[k]-p[i]);<br /> if f+p[l]<f+p[i] then new(k,j,i)<br /> else new(i,j,k);<br /> end;<br /> begin<br /> readln(n);fa[1]:=1;<br /> for i:=1 to n do<br /> read(p[i].x,p[i].y,p[i].z);<br /> init(1,2,3,4);init(1,2,4,3);<br /> init(1,3,4,2);init(2,3,4,1);<br /> for i:=5 to n do begin<br /> j:=next(1);<br /> while j<=t do begin<br /> o[j]:=s[j].f+p[i]<s[j].c;<br /> j:=next(j+1);<br /> end;<br /> j:=next(1);pt:=t;<br /> while j<=pt do begin<br /> if o[j] then with s[j] do begin<br /> for k:=1 to 3 do if not o[e[v[k+1],v[k]]]<br /> then new(v[k],v[k+1],i);<br /> fa[j]:=j+1;<br /> end;<br /> j:=next(j+1);<br /> end;<br /> end;<br /> i:=next(1);<br /> while i<=t do begin<br /> with s[i] do begin<br /> u:=(p[v[2]]-p[v[1]])*(p[v[3]]-p[v[1]]);<br /> ans:=ans+sqrt(u.x*u.x+u.y*u.y+u.z*u.z);<br /> end;<br /> i:=next(i+1);<br /> end;<br /> writeln(ans/2:0:3);<br /> end.<br />