把点集凸包化Granham-Scan算法(使用水平序)概要
- 格式:doc
- 大小:101.00 KB
- 文档页数:7
凸包算法公式凸包是计算几何中的一个重要概念,而凸包算法公式则是解决相关问题的关键工具。
咱先来说说啥是凸包。
想象一下,你面前有一堆散落在地上的钉子,然后你拿一个橡皮筋把最外层的钉子圈起来,让橡皮筋形成的形状能够完全包住所有钉子,这个形状就是这堆钉子的凸包。
凸包算法有好几种,比如 Graham 扫描法、Jarvis 步进法等等。
咱就拿 Graham 扫描法来说说它涉及的公式。
Graham 扫描法里,首先要找到一个基准点。
通常找纵坐标最小的点,如果有多个这样的点,就选横坐标最小的那个。
找到这个点后,其他点就按照和这个基准点的极角大小进行排序。
这里就涉及到计算极角的公式啦。
对于两个点 A(x1, y1)和 B(x2, y2),极角θ 可以通过反正切函数来计算,公式是:θ = atan2(y2 - y1, x2 - x1)。
计算出极角后,就可以开始扫描了。
从基准点开始,依次检查相邻的三个点,如果这三个点构成的转向是逆时针的,那就保留中间那个点;如果是顺时针的,就把中间那个点去掉。
这里判断转向的公式就比较关键了。
对于三个点 A(x1, y1)、B(x2,y2)和 C(x3, y3),可以通过计算向量叉积来判断转向。
如果叉积大于 0 ,就是逆时针;小于 0 ,就是顺时针。
向量叉积的公式是:(x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1) 。
我记得之前有一次参加数学建模比赛,题目就和凸包算法有关。
当时我们小组几个人,一开始对这些公式和算法都不太熟悉,急得像热锅上的蚂蚁。
大家一起熬夜查资料、讨论,一遍遍地推导公式,尝试不同的方法。
特别是在计算极角和判断转向的时候,总是出错。
但经过不断地尝试和纠错,我们终于搞清楚了这些公式的应用,成功解决了问题,还拿到了不错的名次。
总之,凸包算法公式虽然看起来有点复杂,但只要掌握了其中的原理和规律,多做练习,就能熟练运用啦。
不管是在数学研究中,还是在实际的计算机图形学、地理信息系统等领域,凸包算法都有着广泛的应用。
葛立恒扫描法葛立恒扫描法(Graham Scan),又称凸包算法,是解决计算几何问题中的经典算法之一。
它的主要作用是计算多边形或点集的凸包,并返回凸包上的点集。
葛立恒扫描法的时间复杂度为O(nlogn),其中n是输入点集的大小。
凸包是一个简单多边形,可以包含给定点集中的所有点。
它的边界是由点集中的一些点组成的,这些点被称为凸包上的顶点。
凸包在计算几何、图形学以及计算机视觉等领域都有广泛的应用。
葛立恒扫描法的运行过程如下:1. 找到y值最小的点,并将它放在结果集中。
2. 将其余所有点按照与y值最小点的极角进行排序。
3. 对于每个点P,计算它与前两个点的极角。
如果它的角度不在逆时针方向,则将倒数第二个点从结果集中删除,然后重复此过程直到极角正确。
4. 返回结果集。
让我们来详细了解葛立恒扫描法的每个步骤。
找到y值最小的点要找到y值最小的点,我们可以遍历所有点,并找到纵坐标最小的那个。
在这里,我们使用了lambda函数来比较每个点的y值。
```python def find_lowest_point(points): lowest = min(points, key=lambda point: point[1]) return lowest ```排序接下来,我们需要将其余所有点按照与y值最小点的极角进行排序。
为此,我们需要定义一个函数来计算两点之间的极角。
在这里,我们使用了arctan2函数来计算极角。
```python def polar_angle(p1, p2=None): if p2 is None: p2 = lowest_point y_span =p1[1] - p2[1] x_span = p1[0] - p2[0] return atan2(y_span, x_span) ```然后,我们可以使用此函数来排序输入点集。
在这里,我们使用了sorted函数来排序。
```python def sort_points(points):sorted_points = sorted( points,key=cmp_to_key(lambda x,y: 1 if polar_angle(x) < polar_angle(y) else -1) ) returnsorted_points ```计算极角接下来,我们需要为每个点计算它与前两个点的极角。
halcon 凸壳运算-回复什么是凸壳运算?凸壳运算(Convex Hull Operation)是一种在计算机视觉和图像处理领域中常用的几何变换方法。
它通常用于提取二维图像或点云数据中的凸多边形边界,无论是在形状分析、目标检测还是场景重建中,凸壳运算都有广泛的应用。
在凸壳运算中,我们所关注的是一个包围一组点的最小凸多边形,也就是将给定的点集合的外围轮廓封闭起来的最小凸包。
这个凸多边形的顶点是给定点集的子集,且连接这些顶点的线段不会超出其他点。
在图像处理中,凸壳运算可以用来求解物体的边界以及计算物体的面积、周长等特征。
在计算机视觉中,使用凸壳运算可以帮助我们进行目标的形状分析、目标检测以及图像的分割等任务。
此外,在计算机图形学中,凸壳运算还可以用于场景重建、虚拟现实等应用。
凸壳运算的三种方法:在凸壳运算中,存在三种常用的算法,它们分别是:Graham扫描算法、快速增量算法和欧几里得算法。
下面我将分别介绍这三种算法的原理和步骤。
1. Graham扫描算法Graham扫描算法是一种经典的凸壳求解算法。
它的基本原理是选取一个点作为起点(通常是给定点集中最下方的点),然后按照顺时针或逆时针的方式对点进行排序。
接下来,算法使用一个栈来存储凸壳的边界点,栈的初始状态为空。
然后依次处理排序后的点集,对于每个点,依次与栈中的点进行相互连线,并判断当前连线与栈顶元素与栈次顶元素构成的连线之间的夹角。
如果连线的方向和夹角满足逆时针旋转,则将当前点入栈;否则,将栈顶元素出栈。
最后,栈中剩余的点即为凸壳的顶点。
2. 快速增量算法快速增量算法是解决凸壳问题的另一种高效算法。
它的基本思想是从上下左右四个方向选择凸壳的点,分别称为上壳、下壳、左壳和右壳。
首先,将给定点集按照x坐标从小到大进行排序,并将最左边的点设定为第一个凸壳点,将最右边的点设定为第一个凸壳点。
接下来,分别从上述四个方向开始,依次找到凸壳的点。
以从左到右的上壳为例,从左侧的第一个点开始,通过比较两个点之间的斜率来确定是否为凸壳的点。
凸包问题-graham扫描{graham扫描法通过设置一个关于后选点的堆栈s来解决凸包问题。
输入集合Q中的每个点都被压入栈一次,非ch(Q)中的顶点的点最终会被弹出堆栈。
当算法终止时,堆栈s中仅包含ch(Q)中的顶点,其顺序为各点在边界上出现的逆时针方向排列的顺序。
过程graham_scan的输入点集Q,它调用函数top(s),以便在不改变堆栈s的情况下,返回处于栈顶的点,并调用函数next_to_top(s),来返回处于堆栈顶部下面的那个点,切不改变栈s。
} {graham_scan寻找凸报,时间复杂度为O(nlgn),但我用的选择排序,所以成O(n2)的了1、let p0 be the point in Q with the minimum y-coordinate,or the leftmost such point in case of a tie2、let<p1,p2,p3...pm>be the remaining points in Q,sorted by polar angle in counterclockwise order around p0(if more than one point has the same angle,remove all butthe one that is farthest from p03、push(p0,s)4、push(p1,s)5、push(p2,s)6、for i:=3 to m dowhile the angle formed by points next-to-top(s),top(s),and(pi) makes a nonleft trun8、do pop(s)9、push(pi,s),10、retur s}{copyright 陈舒伟,对已知的一些点寻找凸包}program xxxxxx;consteps=1e-6;typetpoint=record//点类型x,y:longint;end;varq:array[1..1000]of tpoint;//初始点级ch:array[1..1000]of tpoint;//最后寸凸包的点的数组qq:array[1..1000]of tpoint;//排序后的点集;co:array[1..1000]of double;//初始coscoo:array[1..1000]of double;//排序后的cosd:array[1..1000]of double;//r,计算cos用x/rdd:array[1..1000]of double;//排序后的rn,tail:longint;procedure find_min_y;{找出y坐标最小点}vari,j:longint;t:tpoint;beginfor i:=2 to n doif (q[1].y>q[i].y)or((q[1].y=q[i].y)and(q[1].x>q[i].x)) thenbegint:=q[1];q[1]:=q[i];q[i]:=t;end;end;procedure cal_cos;//计算点到定点的cos极角;vari:longint;x,y:longint;beginfor i:=2 to n dobeginx:=q[i].x-q[1].x;y:=q[i].y-q[1].y;d[i]:=sqrt(x*x+y*y);co[i]:=x/d[i];end;end;function same(a,b:double):boolean;beginsame:=abs(a-b)<eps;end;procedure sort_and_ok;{根据极角从小到大排序,如果有相同极角的只取最外面的一个}vari,j:longint;x:double;t:tpoint;tt:double;beginfor i:=2 to n-1 dofor j:=i+1 to n doif (co[j]-co[j]>eps)or((same(co[i],co[j]))and(d[i]>d[j])) then begint:=q[i];q[i]:=q[j];q[j]:=t;x:=co[i];co[i]:=co[j];co[j]:=x;tt:=d[i];d[i]:=d[j];d[j]:=tt;end;qq:=q;coo:=co;dd:=d;tail:=n;end;procedure init;//初始化,读数vari:longint;beginread(n);for i:=1 to n doread(q[i].x,q[i].y);find_min_y;//找出凸包的第一个点,y坐标最小点,如果有多个最小,取最左边的;cal_cos;//计算每个点到顶点的cossort_and_ok;//根据cos的值,可以根据极角从小到大排序;end;function area2(pa,pb,pc:tpoint):double;{判断是否符合凸包条件,向量都是向左转,逆时针方向的}beginarea2:=(pb.x-pa.x)*(pc.y-pa.y)-(pc.x-pa.x)*(pb.y-pa.y);end;procedure build;//构建凸包的过程vari,j,k:longint;beginch[1]:=qq[1];ch[2]:=qq[2];ch[3]:=qq[3];//初始化,栈中存三个点j:=3;for i:=4 to tail do//依次扫描后面的点,选取新的点构建凸包beginif area2(ch[j-1],ch[j],qq[i])<0 then//如果新的点又向量右转得到begin//那么肯定不是凸包,对原来的进行一次调整ch[j]:=qq[i];k:=j-1;while area2(ch[k-1],ch[k],ch[j])<0 dobegindec(j);ch[j]:=qq[i];k:=j-1;end;endelse begininc(j);ch[j]:=qq[i];end;end;for i:=1 to j dowriteln(ch[i].x,' ',ch[i].y);end;beginassign(input,'a.in');assign(output,'a.out');reset(input);rewrite(output);init;build;close(output);end.。
凸包算法及凸包融合凸包算法是计算凸包的一种常用算法,它可以找到一组点集中最外层的凸多边形。
凸包融合是指将两个凸包合并成一个新的凸包,能够通过减少顶点数目来优化计算效率。
凸包算法主要有以下几种常见的实现方法:1.枚举算法:对于点集中的每一对点,判断其他点是否位于这两点所确定的直线的一侧。
如果所有点都在一侧,则这两点是凸包上的边。
时间复杂度为O(n^3)。
2. Graham扫描算法:选取一个点作为基准点,将其他点按照相对于基准点的极角大小进行排序。
然后依次处理每个点,判断其是否属于凸包。
时间复杂度为O(nlogn)。
3. Jarvis步进算法(也称为包裹法):从点集中选取一个临时点p,然后找到与p相邻的点集中极角最小的点q,将q加入凸包中。
然后将q作为新的临时点p,重复以上步骤,直到回到第一个点。
时间复杂度为O(nh),其中h是凸包的边数。
4.快速凸包算法:通过空间分割和递归的方法进行凸包计算,时间复杂度为O(nlogn)。
凸包融合是指将两个凸包合并成一个新的凸包,通常需要满足以下条件:1.相交边的共享:两个凸包如果相交,那么它们的公共边必须都在新的凸包中。
2.外部边的合并:如果两个凸包没有相交,那么合并后的凸包应该包含两个凸包的外部边。
3.顺序性:合并后的凸包应该按照某种规定的顺序进行连接。
凸包融合算法的一种常见方法是基于边的融合。
具体步骤如下:1.找到两个凸包之间的最近边,并将其作为起始边。
2.沿着其中一个凸包的边界向对面的凸包前进,每次选取与当前边最接近的边。
3.如果新选取的边与已经选取的边形成了一个角度大于180度的三角形,那么停止前进,并将新选取的边作为起始边。
4.重复步骤2和步骤3,直到回到起始边。
凸包融合算法可以减少凸包的顶点数量,从而提高计算效率。
例如,对于两个有m和n个顶点的凸包,假设m > n,则融合后的凸包最多有m+n个顶点,而不是m*n个顶点。
融合后的凸包可以保留原始凸包的边界信息,并且减少了计算和存储开销。
探求二维凸包及其应用许瑞广,余志伟中国矿业大学(北京)资源学院(100083)E-mail :lucky_xrg@摘 要:凸包是计算几何中最普遍、最基本的一种结构,本文介绍了二维凸包的概念和性质,并介绍几种求二维凸包的方法:Gift-Wrapping 、Graham-Scan 算法,以及这几种算法的正确性和时间复杂度的分析,最后通过两个实例来简要介绍二维凸包的应用。
关键字:凸包、Gift-Wrapping 、Graham-Scan作为计算几何中第一个被深入研究的几何模型,凸包以其优美的性质带来了广泛的应用,本文将对这个几何模型进行简要的介绍。
1. 凸包的概念和性质我们首先从一个实例来引入凸包:假设你种了很多树,想用一个篱笆把所有的树都包在里面,出于经济考虑,显然这个篱笆应该是越小越好。
给出树的坐标,求出篱笆的最小周长。
如图1-1所示的篱笆是一个最小的篱笆,而这个篱笆就是这些树的凸包(Convex Hull)。
图1-1 凸包(Convex Hull)要定义凸包,首先我们来研究一下凸多边形。
定义1 凸多边形Ù整个图形在任一条边的一侧。
定义2 D 是凸多边形ÙD D x x xx ∈+∈∀2,,2121,即对于一个凸多边形任意两个内点的中点也在此图形内。
我们不仅考虑中点,还考虑所有内分点,于是有如下定义。
定义3 D 是凸多边形Ù[]D D x x xx ∈−+∈∀∈∀2121)1(,1,0,,λλλ因此定义2是定义3的一种特殊形式。
如图1-2给出了凸图形和凹图形的图示:图2-2 凸图形和凹图形设S 是平面(E 2)上的点集,用CH(S)表示点集S 的凸包,BCH(S)表示S 的凸包边界。
定义4 平面点集S 的凸包CH(S)是包含S 的最小凸集,凸包上的顶点称为极点。
点集S 的凸包是包含S 的所有凸集的并,或者CH(S)是包含S 的所有半空间的交。
二维中的半空间是半平面,它是指位于一条直线上及该线一侧的点的集合。
平面散乱点集凸包算法详解摘要:本文旨在详细介绍一种用于计算平面上散乱点集的凸包的算法。
凸包算法是计算几何中的一个重要问题,它在图形学、机器学习、图像处理等领域有着广泛的应用。
本文档将详细阐述凸包的概念、性质以及几种常用的凸包算法,包括Graham 扫描法和Chan算法,并对每种算法的时间复杂度进行分析。
1. 引言在计算几何中,凸包问题是研究如何找到一组点的最小凸多边形,该多边形包含了所有的点。
这个问题在很多领域都有应用,比如在机器人学中的碰撞检测、计算机图形学中的渲染优化、以及数据分析中的数据可视化等。
2. 凸包的定义与性质凸包是指包含所有给定点集的最小凸多边形。
凸包具有以下性质:- 凸包是唯一的。
- 凸包的边界上的点(极点)按顺序连接可以构成一个凸多边形。
- 任何不在凸包边界上的点都位于由边界点构成的某个三角形内部。
3. 凸包算法概述有多种算法可以计算凸包,包括Graham扫描法、Chan算法、Andrew算法等。
这些算法各有特点,但大多数都是基于分治策略或贪心策略。
4. Graham扫描法Graham扫描法是一种效率较高的凸包算法,其基本思想是从最低的点开始,按照每个点相对于基准点的极角进行排序,然后依次检查每个点是否会使当前的凸包发生变化。
步骤如下:a. 找到所有点中y坐标最小的点P,如果这样的点有多个,则取x坐标最小的一个。
b. 将其他点按照与P点的极角排序。
c. 从排序后的点集中依次取出点,检查是否会影响当前的凸包。
d. 重复步骤c,直到所有点都被检查过。
5. Chan算法Chan算法是对Graham扫描法的一种改进,它通过减少不必要的比较来提高效率。
Chan算法使用了一个堆栈来存储可能会成为凸包顶点的点。
步骤如下:a. 将所有点按照x坐标排序。
b. 从左到右扫描排序后的点集,使用堆栈来记录可能的凸包顶点。
c. 当扫描到一个新的点时,更新堆栈顶部的点,确保堆栈顶部的点是当前扫描线左侧最远的点。
凸包算法详解Graham扫描法时间复杂度:O(n㏒n)思路:Graham扫描的思想是先找到凸包上的⼀个点,然后从那个点开始按逆时针⽅向逐个找凸包上的点,实际上就是进⾏极⾓排序,然后对其查询使⽤。
步骤:1. 把所有点放在⼆维坐标系中,则纵坐标最⼩的点⼀定是凸包上的点,如图中的P0。
2. 把所有点的坐标平移⼀下,使 P0 作为原点,如上图。
3. 计算各个点相对于 P0 的幅⾓α,按从⼩到⼤的顺序对各个点排序。
当α相同时,距离 P0 ⽐较近的排在前⾯。
例如上图得到的结果为P1,P2,P3,P4,P5,P6,P7,P8。
我们由⼏何知识可以知道,结果中第⼀个点 P1 和最后⼀个点 P8 ⼀定是凸包上的点。
(以上是准备步骤,以下开始求凸包)以上,我们已经知道了凸包上的第⼀个点 P0 和第⼆个点 P1,我们把它们放在栈⾥⾯。
现在从步骤3求得的那个结果⾥,把 P1 后⾯的那个点拿出来做当前点,即 P2 。
接下来开始找第三个点:4. 连接P0和栈顶的那个点,得到直线 L 。
看当前点是在直线 L 的右边还是左边。
如果在直线的右边就执⾏步骤5;如果在直线上,或者在直线的左边就执⾏步骤6。
5. 如果在右边,则栈顶的那个元素不是凸包上的点,把栈顶元素出栈。
执⾏步骤4。
6. 当前点是凸包上的点,把它压⼊栈,执⾏步骤7。
7. 检查当前的点 P2 是不是步骤3那个结果的最后⼀个元素。
是最后⼀个元素的话就结束。
如果不是的话就把 P2 后⾯那个点做当前点,返回步骤4。
最后,栈中的元素就是凸包上的点了。
以下为⽤Graham扫描法动态求解的过程: 下⾯静态求解过程1 #include<iostream>2 #include<string.h>3 #include<algorithm>4 #include<cstdio>5 #include<cmath>6using namespace std;7const int maxn=105;8const double PI=acos(-1.0);9struct node{int x,y;};10 node vex[maxn];//存⼊所有坐标点11 node stackk[maxn];//凸包中所有的点12bool cmp1(node a,node b){//按点的坐标排序13if(a.y==b.y)return a.x<b.x;//如果纵坐标相同,则按横坐标升序排14else return a.y<b.y;//否则按纵坐标升序排15 }16bool cmp2(node a,node b){//以基点为坐标原点,极⾓按升序排,这⾥可⽤atan2函数或者叉积来进⾏极⾓排序,但是⽤atan2函数来排序效率⾼时间快,不过精度⽐叉积低17double A=atan2(a.y-stackk[0].y,a.x-stackk[0].x);//返回的是原点⾄点(x,y)的⽅位⾓,即与x轴的夹⾓18double B=atan2(b.y-stackk[0].y,b.x-stackk[0].x);19if(A!=B)return A<B;//逆时针⽅向为正值,极⾓⼩的排在前⾯20else return a.x<b.x;//如果极⾓相同,则横坐标在前⾯的靠前排列21 }22int cross(node p0,node p1,node p2){//计算两个向量a、b(a=(x1,y1),b=(x2,y2))的叉积公式:a×b=x1y2-x2y1 ===> p0p1=(x1-x0,y1-y0),p0p2=(x2-x0,y2-y0)23return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);24 }25double dis(node a,node b){//计算两点之间的距离26return sqrt((a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y));27 }28int main(){29int t;30while(~scanf("%d",&t)&&t){31for(int i=0;i<t;++i)//输⼊t个点32 scanf("%d%d",&vex[i].x,&vex[i].y);33if(t==1)printf("%.2f\n",0.00);//如果只有⼀个点,则周长为0.0034else if(t==2)printf("%.2f\n",dis(vex[0],vex[1]));//如果只有两个点,则周长为两个点的距离35else{36 memset(stackk,0,sizeof(stackk));//清037 sort(vex,vex+t,cmp1);//先按坐标点的位置进⾏排序38 stackk[0]=vex[0];//取出基点39 sort(vex+1,vex+t,cmp2);//将剩下的坐标点按极⾓进⾏排序,以基点为坐标原点40 stackk[1]=vex[1];//将凸包中的第⼆个点存⼊凸集中41int top=1;//当前凸包中拥有点的个数为top+142for(int i=2;i<t;++i){//不断地找外围的坐标点43while(top>0&&cross(stackk[top-1],stackk[top],vex[i])<=0)top--;//如果叉积为负数或0(0表⽰两向量共线),则弹出栈顶元素44//虽然第2个凸点显然是最外围的⼀点,但加上top>0保证了栈中⾄少有2个凸点45 stackk[++top]=vex[i];46 }47double s=0;48for(int i=1;i<=top;++i)//计算凸包的周长49 s+=dis(stackk[i-1],stackk[i]);50 s+=dis(stackk[top],vex[0]);//最后⼀个点和第⼀个点之间的距离51 printf("%.2f\n",s);52/*53 int s=0;//计算凸包的⾯积54 for(int i=1;i<=top;i++)55 s+=cross(st[i-1],st[i],e[0])/2;56*/57 }58 }59return0;60 }。
把点集凸包化Granham-Scan算法(使用水平序)#include<stdio.h>#include<string.h>#include<math.h>#include<algorithm>using nameaace std;const int M=100000+5;struct Point{double x,y;} p[M];double dis(Point A,Point B){return sqrt((B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y));}bool cmp(Point a,Point b){if (a.x<b.x) return true;if (a.x>b.x) return false;if (a.y<b.y) return true;return false;}double Xdet(Point A,Point B,Point C){double x1,x2,y1,y2;x1=B.x-A.x; y1=B.y-A.y; x2=C.x-A.x; y2=C.y-A.y;return x1*y2-x2*y1; //大于0在左手边,逆时针}bool bo[M];Point pp[M];int stack[M]; //from 1 to tvoid Gram_Scan(Point *p,int &n) //p从1-n,把点集土包化 n*log(n); {int i,t;sort(p+1,p+1+n,cmp);for(t=0,i=1;i<=n;i++){ //合并排序if (i>1 && p[i].x==p[i-1].x && p[i].y==p[i-1].y) continue;p[++t]=p[i];}n=t; t=0;memset(bo+1,true,n*sizeof(bo[0]));if (n>0){stack[++t]=1;bo[stack[t]]=false;}if (n>1){stack[++t]=2;bo[stack[t]]=false;}if (n>2){for(i=3;i<n;i++)if(bo[i] && Xdet(p[stack[t-1]],p[stack[t]],p[i])>=0) stack[++t]=i,bo[i]=false;else{while(t>=2&& Xdet(p[stack[t-1]],p[stack[t]],p[i])<0) bo[stack[t]]=true,t--;stack[++t]=i;bo[stack[t]]=false;}for(i=n;i>=1;i--)if (bo[i] && Xdet(p[stack[t-1]],p[stack[t]],p[i])>=0) stack[++t]=i,bo[i]=false;else{while(t>=2&&Xdet(p[stack[t-1]],p[stack[t]],p[i])<0) bo[stack[t]]=true,t--;stack[++t]=i;bo[stack[t]]=false;}t--;}for(i=1;i<=t;i++) pp[i]=p[stack[i]];memcpy(p+1,pp+1,t*sizeof(Point));n=t;}求凸点集的面积double area(Point *p,int n){double sum=0;int i;p[n+1]=p[1];for(i=1;i<=n;i++)sum+=p[i].x*p[i+1].y-p[i].y*p[i+1].x;return sum/2.0;}const double EPS=1e-9;const double maxn=1e6-1;const double PI=acos(-1.);const int M=100+5;const double offset=11213;#define zero(x) (((x)>0?(x):-(x))<EPS)struct Point{double x,y;} p[M];struct LINESEG{Point st,ed;};struct LINE{double a,b,c;};double dist(Point a,Point b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}double multiply(Point a,Point b,Point c){return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);}double dotmultiply(Point a,Point b,Point c){return (a.x-c.x)*(b.x-c.x)+(a.y-c.y)*(b.y-c.y);}bool online(LINESEG L,Point q){return fabs(multiply(L.ed,q,L.st))<EPS && (q.x-L.st.x)*(q.x-L.ed.x)<EPS && (q.y-L.st.y)*(q.y-L.ed.y)<EPS; }LINE makeline(Point p1,Point p2){LINE tl;tl.a=p2.y-p1.y; tl.b=p1.x-p2.x;tl.c=p1.y*p2.x-p1.x*p2.y;if (tl.a<EPS) tl.a=-tl.a,tl.b=-tl.b,tl.c=-tl.c;return tl;}inline double MAX(double x,double y){return x>y?x:y;}inline double MIN(double x,double y){return x<y?x:y;}bool intersect(LINESEG u,LINESEG v){return MAX(u.st.x,u.ed.x)>=MIN(v.st.x,v.ed.x)&& MAX(v.st.x,v.ed.x)>=MIN(u.st.x,u.ed.x)&& MAX(u.st.y,u.ed.y)>=MIN(v.st.y,v.ed.y)&& MAX(v.st.y,v.ed.y)>=MIN(u.st.y,u.ed.y)&& multiply(v.st,u.ed,u.st)*multiply(u.ed,v.ed,u.st)>=0&& multiply(u.st,v.ed,v.st)*multiply(v.ed,u.ed,v.st)>=0;}bool intersect_A(LINESEG u,LINESEG v){return intersect(u,v) && !online(u,v.st) && !online(u,v.ed)&& !online(v,u.st) && !online(u,v.ed);}bool intersect_L(LINESEG u,LINESEG v){return multiply(u.st,v.ed,v.st)*multiply(v.ed,u.ed,v.st)>=0;}bool intersection_line(LINE L1,LINE L2,Point &inter){ double det=L1.a*L2.b-L2.a*L1.b;if (fabs(det)<EPS) return false;inter.x=(L2.c*L1.b-L1.c*L2.b)/det;inter.y=(L2.a*L1.c-L1.a*L2.c)/det;return true;}bool intersection_lineseg(LINESEG u,LINESEG v,Point &inter){ LINE L1,L2;L1=makeline(u.st,u.ed);L2=makeline(v.st,v.ed);if (intersection_line(L1,L2,inter)) return online(u,inter) && online(v,inter);else return false;}bool intersection_LLS(LINE L1,LINESEG u,Point &inter){ LINE L2;L2=makeline(u.st,u.ed);if (intersection_line(L1,L2,inter))return online(u,inter);else return false;}int Inside(Point q,int n){Point q2;const int on_edge=0;int i=0,count;p[n]=p[0];while (i<n)for(count=0,i=0,q2.x=rand()+offset,q2.y=rand()+offset;i<n;i++)if (zero(multiply(q,p[i],p[i+1])) && (p[i].x-q.x)*(p[i+1].x-q.x)<EPS && (p[i].y-q.y)*(p[i+1].y-q.y)<EPS) return on_edge;else if (zero(multiply(q,q2,p[i]))) break;else if (multiply(q,p[i],q2)*multiply(q,p[i+1],q2)<-EPS &&multiply(p[i],q,p[i+1])*multiply(p[i],q2,p[i+1])<-EPS) count++;return count&1;}bool cmp(Point p,Point q){if (p.x<q.x) return true;if (p.x>q.x) return false;if (p.y<q.y) return true;return false;}//线段与多边形相交定义为至少有1个点在多边形内,返回true; bool LINESEG_intersect_Polygon(LINESEG LS1,int n) {LINESEG LS2;Point mid;int i;int j,top;Point stack[M];p[n]=p[000];for(i=0;i<n;i++){LS2.st=p[i]; LS2.ed=p[i+1];if (intersect_A(LS1,LS2)) return true;}top=0;stack[top++]=LS1.st;stack[top++]=LS1.ed;for(i=0;i<n;i++)if (online(LS1,p[i])) stack[top++]=p[i];sort(stack,stack+top,cmp);stack[top]=stack[0];for(j=0;j<top;j++) {mid.x=(stack[j].x+stack[j+1].x)/2;mid.y=(stack[j].y+stack[j+1].y)/2;if (Inside(mid,n)) return true;}return false;}const int M=15000;struct Line{double a,b,c;}L[M];struct Point{double x,y;} p[M],pp[M];//由两点化一般式Line LineChange(Point P1,Point P2){Line K;K.a=P2.y-P1.y;//(y2-y1)*x+(x1-x2)*y-(x1-x2)*y1-x1*(y2-y1)=0; counterclockK.b=P1.x-P2.x;K.c=-P1.x*K.a-K.b*P1.y;return k;}//求两直线交点bool GetSegcross(Line K1,Line K2,Point &pp){double det=K1.a*K2.b-K2.a*K1.b;if (fabs(det)<1e-8) return 0;pp.x=(K1.b*K2.c-K2.b*K1.c)/det;pp.y=-(K1.a*K2.c-K2.a*K1.c)/det;return 1;}//p在直线上返回0.00double p_on_line(Line K,Point p){return K.a*p.x+K.b*p.y+K.c;}//求两点的垂直平分线void MidLine(Point P1,Point P2,Line &K){K.a=2*(P1.x-P2.x);K.b=2*(P1.y-P2.y);K.c=(-K.a*(P1.x+P2.x)-K.b*(P1.y+P2.y))/2;}//求任意点对的最小距离,分治nlogn.double nearest(Point *p, int n) //p should already be sorted by x{if(n==2) return dist(p[0], p[1]);if(n==1) return INF;int m=p[n/2].x,i,j;double left,right,tmp,ret,t;left=nearest(p,n/2); right=nearest(&p[n/2],n-n/2);ret=tmp =left<right?left:right;for(i=n/2-1; i>=0 && p[i].x>m-tmp_nearest;i--)for(j=n/2; j<n && p[j].x<m+tmp_nearest;j++) {t=dist(p[i],p[j]);if(t<tmp_nearest) ret=t;}return ret;}Euler的任意四面体体积公式(已知边长求体积)已知4点坐标求体积(其中四个点的坐标分别为(x1,y1,z1),(x2,y2,z2),(x3,y3,z3),(x4,y4,z4))11111234(1/6)*.12341234x x x xVy y y yz z z z=22222222222222222222222236.2222p q n p r mpp q n q r lV qp r m q r lr+-+-+-+-=+-+-。