凸包算法代码
⑴ 求二维凸包增量法代码，急，急，急
在网上搜一本书《计算几何算法分析与设计》，里面有具体算法。
⑵ 凸包的发展历史,急需，越详细越好，谢谢！！！！
⒈对于一个集合D，D中任意有限个点的线性组合的全体称为D的凸包。 ⒉对于一个集合D，所有包含D的凸集之交称为D的凸包。 可以证明，上述两种定义是等价的 概念
1 点集Q的凸包（convex hull）是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。右图中由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。 2 一组平面上的点，求一个包含所有点的最小的凸多边形，这就是凸包问题了。这可以形象地想成这样：在地上放置一些不可移动的木桩，用一根绳子把他们尽量紧地圈起来，并且为凸边形，这就是凸包了。编辑本段平面凸包求法常见求法
2.0 Graham's Scan法求解凸包问题
概念 凸包（Convex Hull）是一个计算几何（图形学）中的概念。用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边型，它能包含点集中所有点的。严谨的定义和相关概念参见维基网络：凸包。 这个算法是由数学大师葛立恒（Graham）发明的，他曾经是美国数学学会（AMS）主席、AT&T首席科学家以及国际杂技师协会（IJA）主席。（太汗了，这位大牛还会玩杂技~） 问题 给定平面上的二维点集，求解其凸包。 过程 ⒈ 在所有点中选取y坐标最小的一点H，当作基点。如果存在多个点的y坐标都为最小值，则选取x坐标最小的一点。坐标相同的点应排除。然后按照其它各点p和基点构成的向量<H,p>；与x轴的夹角进行排序，夹角由大至小进行顺时针扫描，反之则进行逆时针扫描。实现中无需求得夹角，只需根据向量的内积公式求出向量的模即可。以下图为例，基点为H，根据夹角由小至大排序后依次为H，K，C，D，L，F，G，E，I，B，A，J。下面进行逆时针扫描。 ⒉ 线段<H,K>；一定在凸包上，接着加入C。假设线段<K,C>；也在凸包上，因为就H，K，C三点而言，它们的凸包就是由此三点所组成。但是接下来加入D时会发现，线段<K,D>；才会在凸包上，所以将线段<K,C>；排除，C点不可能是凸包。 ⒊ 即当加入一点时，必须考虑到前面的线段是否会出现在凸包上。从基点开始，凸包上每条相临的线段的旋转方向应该一致，并与扫描的方向相反。如果发现新加的点使得新线段与上线段的旋转方向发生变化，则可判定上一点必然不在凸包上。实现时可用向量叉积进行判断，设新加入的点为pn + 1，上一点为pn，再上一点为pn - 1。顺时针扫描时，如果向量<pn - 1,pn>；与<pn,pn + 1>；的叉积为正（逆时针扫描判断是否为负），则将上一点删除。删除过程需要回溯，将之前所有叉积符号相反的点都删除，然后将新点加入凸包。 在上图中，加入K点时，由于线段<H,K>；相对于<H,C>；为顺时针旋转，所以C点不在凸包上，应该删除，保留K点。接着加入D点，由于线段<K,D>；相对<H,K>；为逆时针旋转，故D点保留。按照上述步骤进行扫描，直到点集中所有的点都遍例完成，即得到凸包。 复杂度 这个算法可以直接在原数据上进行运算，因此空间复杂度为O⑴。但如果将凸包的结果存储到另一数组中，则可能在代码级别进行优化。由于在扫描凸包前要进行排序，因此时间复杂度至少为快速排序的O(nlgn）。后面的扫描过程复杂度为O(n），因此整个算法的复杂度为O(nlgn）。 ⒉1凸包最常用的凸包算法是Graham扫描法和Jarvis步进法。 对于一个有三个或以上点的点集Q，过程如下： 计算点集最右边的点为凸包的顶点的起点，如上图的P3点。 Do For i = 0 To 总顶点数 计算有向向量P3->Pi If 其余顶点全部在有向向量P3->Pi的左侧或右侧，则Pi点为凸包的下一顶点 Pi点加入凸包列表 GoTo 1 End If Next Exit Do 1: Loop 此过程执行后，点按极角自动顺时针或逆时针排序，只需要按任意两点的次序就可以了。而左侧或右侧的判断可以用前述的矢量点积性质实现。
特殊算法
⒉2求凸包有很多方法，不过最适合OIer和ACMer的估计还是Graham's Scan这个方法了。它的大致方法是这样的：首先，找到所有点中最左边的（y坐标最小的），如果y坐标相同，找x坐标最小的；以这个点为基准求所有点的极角（atan2(y-y0,x-x0）），并按照极角对这些点排序，前述基准点在最前面，设这些点为P[0]..P[n-1]；建立一个栈，初始时P[0]、P[1]、P[2]进栈，对于P[3..n-1]的每个点，若栈顶的两个点与它不构成“向左转”的关系，则将栈顶的点出栈，直至没有点需要出栈以后将当前点进栈；所有点处理完之后栈中保存的点就是凸包了。 如何判断A、B、C构成的关系不是向左转呢？如果b-a与c-a的叉乘小于0就不是。a与b的叉乘就是a.x*b.y-a.y*b.x。 上面的这个Graham的实现比我原来按照USACO里的课文写得简单多了，主要是它通过简单的预处理保证了P[0]、P[1]以及P[n-1]肯定是凸包里的点，这样就可以避免在凸包“绕回来”的时候繁杂的处理。
中心法
先构造一个中心点，然后将它与各点连接起来，按斜率递增的方法，求出凸包上部；再按斜率递减的方法，求出凸包下部。
水平法
从最左边的点开始，按斜率递增的方法，求出凸包上部；再按斜率递减的方法，求出凸包下部。水平法较中心法减少了斜率无限大的可能，减少了代码的复杂度。编辑本段代码例代码一
（在编辑器中将"_ "(下划线+空格）替换成两个空格即可编译； 注意要去掉开通的双字节中文空格，蛋疼的网络。）
⑶ 离散点外包凸多边形生成算法（C#或者C++），要有详细代码和说明，最好有可运行的样例程序好的另外加分，急
find&&find_if
临时对象——构造函数的调用.根据若干个离散点创建最大外包凸多边形图形算法
//卷包裹法---创建最大外包凸多边形
//stdafx.h
#define PI 3.1415926
#define NULL 0
#define LEN sizeof(struct XYpoint)
long pointSum;
struct XYpoint
{
double x;
double y;
struct XYpoint *next;
};
XYpoint *creat(void);
struct XYpoint *insert(struct XYpoint *head2,struct XYpoint *p);
struct XYpoint *del(struct XYpoint *head,struct XYpoint *p);
struct XYpoint *miny(struct XYpoint *head);
double angle(struct XYpoint *a,struct XYpoint *b,struct XYpoint *c);
double dis(struct XYpoint *a,struct XYpoint *b);
struct XYpoint *tank( struct XYpoint *head ,struct XYpoint *head2);
struct XYpoint *convexHull( struct XYpoint *head ,struct XYpoint *head2);
void print(struct XYpoint *head2);
//stdafx.cpp
#include "stdafx.h"
#include <math.h>
#include <vector>
//using namespace std;
struct XYpoint *creat(void)
{
struct XYpoint *head;
struct XYpoint *p1,*p2;
FILE *fp;
if((fp=fopen("in_put.txt","r"))==NULL)
{
printf("can not open the file\n");
exit(0);
}
pointSum=0;
p1=p2=(struct XYpoint *)malloc(LEN);
fscanf(fp,"%lf,%lf",&p1->x,&p1->y);
head=NULL;
while(!feof(fp))
{
pointSum=pointSum+1;
if(pointSum==1)
head=p1;
else
p2->next=p1;
p2=p1;
p1=(struct XYpoint *)malloc(LEN);
fscanf(fp,"%lf,%lf",&p1->x,&p1->y);
}
p2->next=NULL;
fclose(fp);
return(head);
}
struct XYpoint *insert(struct XYpoint *head2,struct XYpoint *p)
{
struct XYpoint *p1,*p0;
p0=p;
p1=head2;
while(p1->next!=NULL)
{
p1=p1->next;
}
p1->next=p0;
p0->next=NULL;
if (head2->next==NULL)
printf("not been insert!\n");
return (head2);
}
struct XYpoint *del(struct XYpoint *head,struct XYpoint *p)
{
struct XYpoint *p0,*p1;
if(head==NULL)
{
printf("\nlist null\n");
goto end;
}
p0=head;
while((p->x!=p0->x||p->y!=p0->y)&&p0->next!=NULL)
{
p1=p0;
p0=p0->next;
}
if(p->x==p0->x&&p->y==p0->y)
{
if(p0==head)
head=p0->next;
else
p1->next=p0->next;
}
else
printf("not been found!\n");
end:
return (head);
}
struct XYpoint *miny(struct XYpoint *head)
{
double min;
struct XYpoint *p,*p1;
p=head;
min=p->y;
p1=p;
p=p->next;
while (p!=NULL)
{
if (min>p->y)
{min=p->y,p1=p;}
else if(min==p->y&&p1->x>p->x)
{min=p->y,p1=p;}
else p=p->next;
}
return(p1);
}
double angle(struct XYpoint *a,struct XYpoint *b,struct XYpoint *c)
{
struct XYpoint *p0,*p1,*p2;
double dsx,dsy,dex,dey,cosfi,norm,fi;
p0=a;
p1=b;
p2=c;
dsx=p1->x-p0->x;
dsy=p1->y-p0->y;
dex=p2->x-p1->x;
dey=p2->y-p1->y;
cosfi=dsx*dex+dsy*dey;
norm=(dsx*dsx+dsy*dsy)*(dex*dex+dey*dey);
cosfi/=sqrt( norm );
fi=acos(cosfi);
if(cosfi<=-1) fi=PI;
if(cosfi>=1) fi=0;
return(fi);
}
double dis(struct XYpoint *a,struct XYpoint *b)
{
struct XYpoint *p1,*p2;
double dsx,dsy,dx;
p1=a;
p2=b;
dsx=p2->x-p1->x;
dsy=p2->y-p1->y;
dx=sqrt(dsx*dsx+dsy*dsy);
return(dx);
}
struct XYpoint *tank( struct XYpoint *head ,struct XYpoint *head2)
{
double minfi,fi;
double dx,dy;
struct XYpoint *p,*p1,*p2;
p2=p=head;
p1=head2;
minfi=PI;
while(p!=NULL)
{
dx=p->x-p1->x;
dy=p->y-p1->y;
if(dx!=0)
{
fi=atan(dy/dx);
if(fi<0)
fi=fi+PI;
}
else if(dx==0&&dy==0) fi=PI;
else fi=PI/2.0;
if(minfi>=fi)
{
minfi=fi;p2=p;
}
p=p->next;
}
return (p2);
}
struct XYpoint *convexHull( struct XYpoint *head ,struct XYpoint *head2)
{
double min;
double tempAngle;
struct XYpoint *lastP,*nowP,*p,*p1,*p2;
p=head;
nowP=p1=head2;
lastP=nowP;
p1=p1->next;
nowP=p1;
while(p1->next!=NULL)
{
p1=p1->next;
lastP=nowP;
nowP=p1;
}
min=angle(lastP,nowP,p);
p2=p;
p=p->next;
while(p!=NULL)
{
tempAngle=angle(lastP,nowP,p);
if (min>tempAngle)
{
min=tempAngle;
p2=p;
p=p->next;
}
else if(min==tempAngle)
{
if(dis(nowP,p2)<dis(nowP,p))
p2=p;
p=p->next;
}
else
{
p=p->next;
}
}
return(p2);
}
void print(struct XYpoint *head2)
{
FILE *fp;
struct XYpoint *p;
p=head2;
if((fp=fopen("out_put.txt","w"))==NULL)
{
printf("can not open the file\n");
exit(0);
}
fprintf(fp,"%ld",pointSum);
fprintf(fp,"\n");
while(p!=NULL)
{
fprintf(fp,"%lf,%lf",p->x,p->y);
fprintf(fp,"\n");
p=p->next;
}
fclose(fp);
}
/*
int _tmain(int argc, _TCHAR* argv[])
{
struct XYpoint *head ,*head2,*pp,*qq;
head=creat();
pp=miny(head);
head2=(struct XYpoint *)malloc(LEN);
head2->x=pp->x;
head2->y=pp->y;
head2->next=NULL;
pp=tank(head,head2);
qq=(struct XYpoint *)malloc(LEN);
qq->x=pp->x;
qq->y=pp->y;
qq->next=NULL;
head2=insert(head2,qq);
head=del(head,pp);
pp=convexHull(head,head2);
do
{
qq=(struct XYpoint *)malloc(LEN);
qq->x=pp->x;
qq->y=pp->y;
qq->next=NULL;
head2=insert(head2,qq);
head=del(head,pp);
pp=convexHull(head,head2);
}while(!(head2->x==pp->x&&head2->y==pp->y));
print(head2);
return 0;
}
*/
//view.h
class CCreateHullView : public CView
{
private:
int m_nPtnum;
XYpoint *m_pPtHead;
XYpoint *m_pHullHead;
};
//view.cpp
CCreateHullView::CCreateHullView()
{
// TODO: add construction code here
m_nPtnum = 0;
m_pPtHead = NULL;
m_pHullHead = NULL;
}
CCreateHullView::~CCreateHullView()
{
if (m_nPtnum > 0)
{
XYpoint *p = m_pPtHead;
while (NULL != p)
{
m_pPtHead = p->next;
p->next = NULL;
delete p;
p = m_pPtHead;
}
m_pPtHead = NULL;
m_nPtnum = 0;
p = m_pHullHead;
while (NULL != p)
{
m_pHullHead = p->next;
p->next = NULL;
delete p;
p = m_pHullHead;
}
m_pHullHead = NULL;
}
}
void CCreateHullView::OnLButtonDown(UINT nFlags, CPoint point)
{
// TODO: Add your message handler code here and/or call default
if (0 == m_nPtnum)
{
m_pPtHead = new XYpoint;
m_pPtHead->x = point.x;
m_pPtHead->y = point.y;
m_pPtHead->next = NULL;
m_nPtnum++;
}
XYpoint *p = new XYpoint;
p->x = point.x;
p->y = point.y;
p->next = m_pPtHead;
m_pPtHead = p;
m_nPtnum++;
Invalidate();
CView::OnLButtonDown(nFlags, point);
}
void CCreateHullView::OnCreateHull()
{
// TODO: Add your command handler code here
if (0 < m_nPtnum)
{
struct XYpoint *head ,*head2,*pp,*qq;
head = m_pPtHead;
pp = miny(head);
head2=(struct XYpoint *)malloc(LEN);
head2->x=pp->x;
head2->y=pp->y;
head2->next=NULL;
pp=tank(head,head2);
qq=(struct XYpoint *)malloc(LEN);
qq->x=pp->x;
qq->y=pp->y;
qq->next=NULL;
head2=insert(head2,qq);
head=del(head,pp);
pp=convexHull(head,head2);
do
{
qq=(struct XYpoint *)malloc(LEN);
qq->x=pp->x;
qq->y=pp->y;
qq->next=NULL;
head2=insert(head2,qq);
head=del(head,pp);
pp=convexHull(head,head2);
}while(!(head2->x==pp->x&&head2->y==pp->y));
//print(head2);
m_pHullHead = head2;
Invalidate();
}
}
void CCreateHullView::OnDraw(CDC* pDC)
{
CCreateHullDoc* pDoc = GetDocument();
ASSERT_VALID(pDoc);
// TODO: add draw code for native data here
XYpoint *p = NULL;
if (0 < m_pHullHead)
{
p = m_pHullHead;
pDC->Rectangle((int)(m_pHullHead->x) - 2, (int)(m_pHullHead->y) - 2, (int)(m_pHullHead->x) + 2, (int)(m_pHullHead->y) + 2);
pDC->MoveTo((int)(m_pHullHead->x), (int)(m_pHullHead->y));
p = m_pHullHead->next;
while (NULL != p)
{
pDC->Rectangle(
(int)(p->x) - 2,
(int)(p->y) - 2,
(int)(p->x) + 2,
(int)(p->y) + 2
);
pDC->LineTo(CPoint((int)p->x, (int)p->y));
p = p->next;
}
p = m_pHullHead;
pDC->LineTo(CPoint((int)p->x, (int)p->y));
}
p = m_pPtHead;
while (NULL != p)
{
pDC->Rectangle(
(int)(p->x) - 2,
(int)(p->y) - 2,
(int)(p->x) + 2,
(int)(p->y) + 2
);
// pDC->FillSolidRect(
// (int)(p->x) - 2,
// (int)(p->y) - 2,
// (int)(p->x) + 2,
// (int)(p->y) + 2,
// RGB(225, 0, 0)
// );
p = p->next;
}
}
不知道可以不，应该可以运行吧，你先试试
⑷ 凸包问题（c++） 输出时就不对了！求各位大侠解决！！
具体的算法代码没看，这可以在网上搜到的，目测你的代码问题是main方法里的p数组是从1开始计数的，也就是数组的第一个是空的，但是tubao方法中是从0开始运算的，所以肯定会出数据错误。下面是我找的凸包问题的代码，可以借鉴下。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
#define N 20
#define inf 1e-6
typedef struct
{
int x;
int y;
}point;
point points[N]; //点集
point chs[N]; //栈
int sp; //栈顶指针
//计算两点之间距离
double dis(point a, point b)
{
return sqrt((a.x - b.x) * (a.x - b.x) * 1.0 + (a.y - b.y) * (a.y - b.y));
}
//通过矢量叉积求极角关系（p0p1）(p0p2)
//k > 0 ,p0p1在p0p2顺时针方向上
double multi(point p0, point p1, point p2)
{
return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}
int cmp(const void *p, const void *q)
{
point a = *(point *)p;
point b = *(point *)q;
double k = multi(points[0], a, b);
if(k < -inf)
return 1;
else if(fabs(k) < inf && (dis(a, points[0]) - dis(b, points[0])) > inf) //两点在同一直线上的话，用最近的
return 1;
else return -1;
}
void convex_hull(int n)
{
int i, k, d;
int miny = points[0].y, index = 0;
for(i=1; i<n; i++) //找最左下顶点
{
if(points[i].y < miny) //找到y坐标最小的点
{
miny = points[i].y;
index = i;
}
else if(points[i].y == miny && points[i].x < points[index].x) //相同的话找到x最小的
{
index = i;
}
}
//把最左下顶点放到第一个
point temp;
temp = points[index];
points[index] = points[0];
points[0] = temp;
qsort(points+1, n-1, sizeof(points[0]), cmp); //p[1:n-1]按相对p[0]的极角从小到大排序
chs[0] = points[n-1];
chs[1] = points[0];
sp = 1;
k = 1;
while(k <= n-1)
{
double d = multi(chs[sp], chs[sp-1], points[k]);
if(d <= 0)
{
sp++;
chs[sp] = points[k];
k++;
}
else sp--;
}
}
int main()
{
int i, j, n;
float sum, area;
freopen("in.txt", "r", stdin);
scanf("%d", &n);
for(i=0; i<n; i++)
scanf("%d%d", &points[i].x, &points[i].y);
convex_hull(n);
for(i=0; i<=sp; i++)
printf("(%d, %d) \n ", chs[i].x, chs[i].y);
sum = 0;
for(i=1; i<=sp; i++) //求周长
sum += dis(chs[i-1], chs[i]);
sum += dis(chs[0], chs[sp]);
printf("周长：%f\n", sum);
area = 0;
for(i=1; i<sp; i++) //求面积
{
double k = multi(chs[0], chs[i], chs[i+1]); //三角形面积是向量叉积的1/2
area += k;
}
area = fabs(area) / 2;
printf("面积：%f\n", area);
getch();
return 0;
}
⑸ ACM 凸包 算法
先解释下凸包 顾名思义 就是多边形是凸的 没有某个点是凹进多边形内部的 哈 文字我也描述不清楚 在高等数学里就有凸的定义 二次导数恒不小于0
再者 就是凸包算法的定义了 凸包算法一般就是计算能包裹住一个点集的最小的凸多边形
至于具体的算法 有很多 也不贴过来了 请看这篇帖子 伪代码比较容易看懂算法的原理
http://www.blogjava.net/sishuiweilan/archive/2007/10/10/151671.html
不懂的地方请追问
⑹ 如何用VB实现凸包算法 我要程序
凸包算法
在制图学的Tin构建中常用,算法很复杂.
你出1000分我可以考虑以下.
⑺ 凸包的平面求法
这个算法是由数学大师葛立恒（Graham）发明的，他曾经是美国数学学会（AMS）主席、AT&T首席科学家以及国际杂技师协会（IJA）主席。
问题
给定平面上的二维点集，求解其凸包。
过程
⒈ 在所有点中选取y坐标最小的一点H，当作基点。如果存在多个点的y坐标都为最小值，则选取x坐标最小的一点。坐标相同的点应排除。然后按照其它各点p和基点构成的向量<H,p>；与x轴的夹角进行排序，夹角由大至小进行顺时针扫描，反之则进行逆时针扫描。实现中无需求得夹角，只需根据余弦定理求出向量夹角的余弦值即可。以下图为例，基点为H，根据夹角由小至大排序后依次为H，K，C，D，L，F，G，E，I，B，A，J。下面进行逆时针扫描。
⒉ 线段<H,K>；一定在凸包上，接着加入C。假设线段<K,C>；也在凸包上，因为就H，K，C三点而言，它们的凸包就是由此三点所组成。但是接下来加入D时会发现，线段<K,D>；才会在凸包上，所以将线段<K,C>；排除，C点不可能是凸包。
⒊ 即当加入一点时，必须考虑到前面的线段是否会出现在凸包上。从基点开始，凸包上每条相临的线段的旋转方向应该一致，并与扫描的方向相反。如果发现新加的点使得新线段与上线段的旋转方向发生变化，则可判定上一点必然不在凸包上。实现时可用向量叉积进行判断，设新加入的点为pn + 1，上一点为pn，再上一点为pn - 1。顺时针扫描时，如果向量<pn - 1,pn>；与<pn,pn + 1>；的叉积为正（逆时针扫描判断是否为负），则将上一点删除。删除过程需要回溯，将之前所有叉积符号相反的点都删除，然后将新点加入凸包。
在上图中，加入K点时，由于线段<H,C>要旋转到<H,K>的角度，为顺时针旋转，所以C点不在凸包上，应该删除，保留K点。接着加入D点，由于线段<K,D>要旋转到<H,K>的角度，为逆时针旋转，故D点保留。按照上述步骤进行扫描，直到点集中所有的点都遍历完成，即得到凸包。
复杂度
这个算法可以直接在原数据上进行运算，因此空间复杂度为O⑴。但如果将凸包的结果存储到另一数组中，则可能在代码级别进行优化。由于在扫描凸包前要进行排序，因此时间复杂度至少为快速排序的O(nlgn）。后面的扫描过程复杂度为O(n），因此整个算法的复杂度为O(nlgn）。 对于一个有三个或以上点的点集Q，过程如下：
计算点集最右边的点为凸包的顶点的起点，如上图的P3点。
Do
For i = 0 To 总顶点数
计算有向向量P3->Pi
If 其余顶点全部在有向向量P3->Pi的左侧或右侧，则Pi点为凸包的下一顶点
Pi点加入凸包列表
GoTo 1
End If
Next
Exit Do
1:
Loop
此过程执行后，点按极角自动顺时针或逆时针排序，只需要按任意两点的次序就可以了。而左侧或右侧的判断可以用前述的矢量点积性质实现。 constpi=3.1415926575;zero=1e-6;maxn=1000;maxnum=100000000;varans,temp:extended;n,tot:longint;x,y:array[0..maxn]ofextended;zz,num:array[0..maxn]oflongint;procereswap(varii,jj:extended);vart:extended;begint:=ii;ii:=jj;jj:=t;end;procereinit;vari,j:longint;beginreadln(n);fori:=1tondoreadln(x[i],y[i]);end;functionok(x,midx,y,midy:extended):longint;beginifabs(x-midx)<=zerothenbeginifabs(midy-y)<=zerothenexit(0);ifmidy>ythenexit(1)elseexit(2);endelsebeginifx<midxthenexit(1)elseexit(2);end;end;procereqsort(head,tail:longint);vari,j:longint;midx,midy:extended;begini:=head;j:=tail;midx:=x[(head+tail)div2];midy:=y[(head+tail)div2];repeatwhileok(x[i],midx,y[i],midy)=1doinc(i);whileok(x[j],midx,y[j],midy)=2dodec(j);ifi<=jthenbeginswap(x[i],x[j]);swap(y[i],y[j]);inc(i);dec(j);end;untili>j;ifi<tailthenqsort(i,tail);ifj>headthenqsort(head,j);end;functionPlot(x1,y1,x2,y2:extended):extended;beginPlot:=x1*y2-x2*y1;end;functioncheck(first,last,new:longint):boolean;varax,ay,bx,by:extended;Pt:extended;beginax:=x[last]-x[first];ay:=y[last]-y[first];bx:=x[new]-x[first];by:=y[new]-y[first];ifPlot(ax,ay,bx,by)<=0thenexit(true)elseexit(false);end;procereTbao;vari,j,tail:longint;begintot:=0;zz[1]:=1;tail:=1;fori:=2tondobeginwhile(zz[tail]<>1)andcheck(zz[tail-1],zz[tail],i)dodec(tail);inc(tail);zz[tail]:=i;end;inc(tot,tail-1);fori:=1totail-1donum[i]:=zz[i];zz[1]:=n;tail:=1;fori:=n-1downto1dobeginwhile(zz[tail]<>n)andcheck(zz[tail-1],zz[tail],i)dodec(tail);inc(tail);zz[tail]:=i;end;fori:=1totail-1donum[tot+i]:=zz[i];inc(tot,tail-1);end;functiondist(a,b:longint):extended;begindist:=sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));end;proceremain;vari,j:longint;beginqsort(1,n);Tbao;ans:=0;fori:=1totot-1doans:=ans+dist(num[i],num[i+1]);ans:=ans+dist(num[tot],num[1]）;ans:=ans+temp*pi*2;writeln(ans:0:1);end;begininit;main;end.
⑻ 求二维凸包的增量算法，最好能详细解释一下
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef double Type; // 注意下面的fabs().
const int maxn = 1005;
const double EPS = 1e-8;
const double Pi = acos(-1.0);
struct Point
{
Type x, y;
Point () {}
Point (Type & xx, Type & yy) : x(xx), y(yy) {}
};
// 判断正负.
int dblcmp(Type d)
{
if (fabs(d) < EPS) return 0; // 注意数据类型不同，abs()也不同.
return d > 0 ? 1 : -1;
}
// 叉乘.
// cross proct of (c->a) and (c->b).
Type Cross(Point & c, Point a, Point b)
{
return (a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y);
}
Type Distance(Point & u, Point & v)
{
return sqrt( 0.0 + (u.x - v.x) * (u.x - v.x) + (u.y - v.y) * (u.y - v.y) );
}
int n;
Point point[maxn];
int Stack[maxn];
int top;
double ans;
bool cmp(const Point & a, const Point & b)
{
if (a.y == b.y) return a.x < b.x;
return a.y < b.y;
}
void graham_scan(void)
{
int i;
int temp_top;
if (n <= 1)
{
top = 0;
return ;
}
sort(point, point + n, cmp); // point[0]即为起点.
// 做右链.
top = -1;
Stack[++top] = 0; Stack[++top] = 1;
for (i = 2; i < n; i++)
{
while (top >= 1 && dblcmp(Cross(point[Stack[top - 1]], point[i], point[Stack[top]])) >= 0) top--; // 如果不能左转，则退栈. 如果只要求极点，则共线的点也是不要的(即要加等于).
Stack[++top] = i;
}
temp_top = top; // 此时的栈顶元素一定是第n个点.
// 做左链.
Stack[++top] = n - 2;
for (i = n - 3; i >= 0; i--)
{
while (top >= temp_top + 1 && dblcmp(Cross(point[Stack[top - 1]], point[i], point[Stack[top]])) >= 0) top--; // 如果不能左转，则退栈. 如果只要求极点，则共线的点也是不要的(即要加等于).
Stack[++top] = i;
}
// 此时的栈顶元素是第1个点.(如果凸包是一条直线，则左右链倒置相同.)
// 凸包的顶点为point[Stack[0]] 到 point[Stack[top - 1]].
}
int main(void)
{
int i;
scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%lf %lf", &point[i].x, &point[i].y);
}
graham_scan();
ans = 0;
for (i = 0; i < top; i++)
{
printf("%lf %lf\n", point[Stack[i]].x, point[Stack[i]].y);
ans += Distance(point[Stack[i]], point[Stack[i + 1]]); // point[Stack[top]] = point[Stack[0]].
}
printf("%lf\n", ans);
return 0;
}
/******************************************************************************************************************************************************/
/******************************************************************************************************************************************************/
/******************************************************************************************************************************************************/
/******************************************************************************************************************************************************/
/******************************************************************************************************************************************************/
/******************************************************************************************************************************************************/
/******************************************************************************************************************************************************/
/******************************************************************************************************************************************************/
/* 按照lrj的黑书来写的.
适用条件：简单多边形(点按顺时针或逆时针给出).
复杂度：O(n).
*/
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef double Type; // 注意下面的fabs().
const int maxn = 1005;
const double EPS = 1e-8;
const double Pi = acos(-1.0);
struct Point
{
Type x, y;
Point () {}
Point (Type & xx, Type & yy) : x(xx), y(yy) {}
};
// 判断正负.
int dblcmp(Type d)
{
if (fabs(d) < EPS) return 0; // 注意数据类型不同，abs()也不同.
return d > 0 ? 1 : -1;
}
// 叉乘.
// cross proct of (c->a) and (c->b).
Type Cross(Point & c, Point a, Point b)
{
return (a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y);
}
Type Distance(Point & u, Point & v)
{
return sqrt( 0.0 + (u.x - v.x) * (u.x - v.x) + (u.y - v.y) * (u.y - v.y) );
}
int n;
Point point[maxn];
int Stack[2 * maxn]; // 两头栈.
int bot, top; // 栈底，栈顶.
double ans;
void Melkman(void)
{
int i;
int temp;
Stack[n] = 0;
// 注意：前三个点不能是共线的.
for (i = 1; i < n; i++)
{
Stack[n + 1] = i; // 当三点平行时要的是后一个点.
if (dblcmp(Cross(point[Stack[n]], point[Stack[n + 1]], point[i + 1]))) break; // 前三个点不共线.
}
bot = n, top = n + 1;
Stack[++top] = Stack[--bot] = i + 1;
// 保证开始的三个点成右手系，否则交换Stack[n]和Stack[n + 1] .
if (dblcmp(Cross(point[Stack[n]], point[Stack[n + 1]], point[Stack[n + 2]])) < 0)
{
temp = Stack[n]; Stack[n] = Stack[n + 1]; Stack[n + 1] = temp;
}
// 维护栈里的点为右手系(即栈中任意连续三点组成的路径是左旋的，或成直线).
for (i = i + 2; i < n; i++)
{
if (dblcmp(Cross(point[Stack[top - 1]], point[Stack[top]], point[i])) > 0 &&
dblcmp(Cross(point[Stack[bot]], point[Stack[bot + 1]], point[i])) > 0)
{ // 如果该点对于栈顶左旋且对于栈底右旋，则说明该点在凸包内.
continue;
}
while (dblcmp(Cross(point[Stack[top - 1]], point[Stack[top]], point[i])) <= 0) top--;
Stack[++top] = i;
while (dblcmp(Cross(point[Stack[bot]], point[Stack[bot + 1]], point[i])) <= 0) bot++;
Stack[--bot] = i;
}
}
int main(void)
{
int i;
scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%lf %lf", &point[i].x, &point[i].y);
}
Melkman(); // 得到的凸包点序列也是按极角序的.
cout << top - bot << endl;
for (i = bot; i < top; i++)
{
printf("%lf %lf\n", point[Stack[i]].x, point[Stack[i]].y);
ans += Distance(point[Stack[i]], point[Stack[i + 1]]); // Stack[top]为第1个点.
}
printf("%lf\n", ans);
return 0;
}
⑼ 请问凸包算法的时间复杂度的测试代码怎么写
代码一
（在编辑器中将"_ "(下划线+空格）替换成两个空格即可编译； 注意要去掉开通的双字节中文空格，蛋疼的网络。）
#include <iostream>
#include <algorithm>
using namespace std;
struct point
{
_ _ int x;
_ _ int y;
} p[30005],res[30005];//p标记图中所有的点，res标记凸包上的点
int cmp(point p1,point p2）
{
_ _ return p1.y < p2.y || (p1.y == p2.y && p1.x < p2.x);
}
bool ral(point p1,point p2,point p3） //用叉乘判断点的位置
{
_ _ return (p2.x - p1.x)*(p3.y - p1.y) > (p3.x - p1.x)*(p2.y - p1.y);
}
int main()
{
_ _ int n,i;
_ _ while(scanf("%d",&n) != EOF) //一共有n个点
_ _ {
_ _ _ _ for(i = 0; i < n; i++)
_ _ _ _ _ _ scanf("%d%d",&p[i].x,&p[i].y);
__ _ _ if(n == 1）
_ _ _ _ {
_ _ _ _ _ _ printf("%d %d\n",p[0].x,p[0].y);
_ _ _ _ _ _ continue;
_ _ _ _ }
_ _ _ _ if(n == 2）
_ _ _ _ {
_ _ _ _ _ _ printf("%d %d\n",p[0].x,p[0].y);
_ _ _ _ _ _ printf("%d %d\n",p[1].x,p[1].y);
_ _ _ _ _ _ continue;
_ _ _ _ }
_ _ _ _ sort(p,p + n,cmp);
_ _ _ _ res[0] = p[0];
_ _ _ _ res[1] = p[1];
_ _ _ _ int top = 1;
_ _ _ _ for(i = 2; i < n; i++)
_ _ _ _ {
_ _ _ _ _ _ while(top && !ral(res[top],res[top - 1],p[i]))
_ _ _ _ _ _ top--;
_ _ _ _ _ _ res[++top] = p[i];
_ _ _ _ }
_ _ _ _ int len = top;
_ _ _ _ res[++top] = p[n - 2];
_ _ _ _ for(i = n - 3; i >= 0; i--)
_ _ _ _ {
_ _ _ _ _ _ while(top != len && !ral(res[top],res[top - 1],p[i]))
_ _ _ _ _ _ top--;
_ _ _ _ _ _ res[++top] = p[i];
_ _ _ _ }
_ _ _ _ for(i = 0; i < top; i++)
_ _ _ _ _ _ printf("%d %d\n",res[i].x,res[i].y);//输出凸包上的点
_ _ }
_ _ return 0;
}
代码二
#include <iostream> // 求点集合的凸包的gram算法。n是顶点个数，x,y是顶点
坐标。
#include <fstream> // order 是按照顶点和左下脚的角度的排序后数组。
#include <deque> // tu即是逆时针的凸包上的顶点。
#include <math.h> //
using namespace std; //使用条件：1。点可以任意给，可重复。
// 2。三个以及以上的点。
ifstream fin("input.txt"); // 3。已经考虑了边上有点的情况。
#define NN 1000
#define pi 3.1415827
typedef struct Cseg{
double x,y,tg;
}Cseg;
int n;
double x[NN],y[NN];
deque <Cseg> order;
deque <int> tu;
Cseg seg1;
deque <Cseg> ::iterator p1;
deque <int> ::iterator p,q;
void in();
void gram();
void makeorder(int s);
double dist(double x1,double yy1,double x2,double yy2）；
double cross(double x1,double yy1,double x2,double yy2）；
void out();
int main()
{
in();
gram();
out();
return 0;
}
void out()
{
int i;
for (i=0;i<tu.size();i++){
cout<<order[tu].x<<" "<<order[tu].y<<endl;
}
cout<<tu.size()<<" Edges Polydgon"<<endl;
return;
}
void in()
{
int i;
fin>>n;
for (i=0;i<n;i++)
fin>>x>>y;
return;
}
void gram()
{
int i,mm;
mm=0;
for (i=1;i<n;i++)
if (y[mm]>y+1e-9） mm=i;
else if (fabs(y[mm]-y)<1e-9 && x[mm]>x+1e-9） mm=i;
makeorder(mm);
seg1.x=x[mm];
seg1.y=y[mm];
tu.clear();
tu.push_back(0);
tu.push_back⑴；
tu.push_back⑵；
for (i=3;i<order.size();i++){
p=tu.end();
seg1.x=order.x;
seg1.y=order.y;
p--;
q=p-1;
if
（cross(order[*p].x-order[*q].x,order[*p].y-order[*q].y,order.x-order[*
q].x,order.y-order[*q].y)>1e-9）
tu.push_back(i);
else{
tu.pop_back();
i--;
continue;
//tu.push_back(i);
}
}//for
return;
}
void makeorder(int s)
{
int i;
double tg;
order.clear();
for (i=0;i<n;i++){
if (i==s) continue;
tg=atan2(y-y[s],x-x[s]);
seg1.x=x;
seg1.y=y;
seg1.tg=tg;
p1=order.begin();
while (p1!=order.end()){
if (fabs(tg-p1->tg)<1e-9）{
if
（dist(x[s],y[s],x,y)>dist(x[s],y[s],p1->x,p1->y)+1e-9） {
p1->x=x;
p1->y=y;
}
break;
}
else
if (tg<p1->tg){
order.insert(p1,seg1）；
break;
}
p1++;
}//while
if (p1==order.end()) order.insert(p1,seg1）；
}//for
seg1.x=x[s];seg1.y=y[s];
order.insert(order.begin(),seg1）；
//for (i=0;i<order.size();i++)
// printf("i=%d %lf %lf
%lf\n",i,order.x,order.y,order.tg*180/pi);
return;
}
double cross(double x1,double yy1,double x2,double yy2）
{
return (x1*yy2-x2*yy1）；
}
double dist(double x1,double yy1,double x2,double yy2）
{
return pow((x1-x2）*(x1-x2）+(yy1-yy2）*(yy1-yy2），0.5）；
}
代码三
P标程{pku 1113 }
{$Q-,S-,R-}
const
pi=3.1415926575;
zero=1e-6;
maxn=1000;
maxnum=100000000;
var
ans,temp :extended;
n,tot :longint;
x,y :array[0..maxn]of extended;
zz,num :array[0..maxn]of longint;
procere swap(var ii,jj:extended);
var
t :extended;
begin
t:=ii;ii:=jj;jj:=t;
end;
procere init;
var
i,j :longint;
begin
readln(n,temp);
for i:=1 to n do readln(x[i],y[i]);
end;
function ok(x,midx,y,midy:extended):longint;
begin
if abs(x-midx)<=zero then
begin
if abs(midy-y)<=zero then exit(0);
if midy>y then exit⑴
else exit⑵；
end
else
begin
if x<midx then exit⑴
else exit⑵；
end;
end;
procere qsort(head,tail:longint);
var
i,j :longint;
midx,midy :extended;
begin
i:=head;
j:=tail;
midx:=x[(head+tail) div 2];
midy:=y[(head+tail) div 2];
repeat
while ok(x[i],midx,y[i],midy)=1 do inc(i);
while ok(x[j],midx,y[j],midy)=2 do dec(j);
if i<=j then
begin
swap(x[i],x[j]);
swap(y[i],y[j]);
inc(i);
dec(j);
end;
until i>j;
if i<tail then qsort(i,tail);
if j>head then qsort(head,j);
end;
function Plot(x1,y1,x2,y2:extended):extended;
begin
Plot:=x1*y2-x2*y1;
end;
function check(first,last,new:longint):boolean;
var
ax,ay,bx,by :extended;
Pt :extended;
begin
ax:=x[last]-x[first];ay:=y[last]-y[first];
bx:=x[new]-x[first];by:=y[new]-y[first];
if Plot(ax,ay,bx,by)<-zero then exit(true)
else exit(false);
end;
procere Tbao;
var
i,j,tail :longint;
begin
tot:=0;
zz[1]:=1;tail:=1;
for i:=2 to n do
begin
while (zz[tail]<>1）and check(zz[tail-1],zz[tail],i) do dec(tail);
inc(tail);
zz[tail]:=i;
end;
inc(tot,tail-1）；
for i:=1 to tail-1 do
num[i]:=zz[i];
zz[1]:=n;tail:=1;
for i:=n-1 downto 1 do
begin
while (zz[tail]<>n)and check(zz[tail-1],zz[tail],i) do dec(tail);
inc(tail);
zz[tail]:=i;
end;
for i:=1 to tail-1 do
num[tot+i]:=zz[i];
inc(tot,tail-1）；
end;
function dist(a,b:longint):extended;
begin
dist:=sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
end;
procere main;
var
i,j :longint;
begin
qsort（1,n);
Tbao;
ans:=0;
for i:=1 to tot-1 do
ans:=ans+dist(num[i],num[i+1]);
ans:=ans+dist(num[tot],num[1]);
ans:=ans+temp*pi*2;
writeln(ans:0:0);
end;
begin
init;
main;
end.
⑽ pascal高维凸包
最简单的：暴力法= =
然后就有包裹法，加点法，一大堆，你要要就在HI上找我，给你发资料