凸包硬币算法
Ⅰ 请问凸包算法的时间复杂度的测试代码怎么写
代码一
（在编辑器中将"_ "(下划线+空格）替换成两个空格即可编译； 注意要去掉开通的双字节中文空格，蛋疼的网络。）
#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.
Ⅱ 求二维凸包的增量算法，最好能详细解释一下
#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;
}
Ⅲ 空间点集的带权Delaunay三角化算法
构造点集的Delaunay三角化的着名增量算法有两种：一种称为局部变换法（也称为Flip-ping算法），另外一种称为Bowyer/Watson算法。构造空间点集的带权Delaunay三角化算法也主要有两种，分别是以上两种算法的推广。我们只介绍推广后的Bowyer/Watson算法，称之为“带权Delaunay空洞算法构造点集的带权Delaunay三角化”算法。
1.带权Delaunay空洞定义
给定Ed空间的点集S，设有一点p∉S位于点集S的凸包中。Δ=ΔT是点集S的带权Delaunay三角化中的任意一个单纯形，z=z（Δ）为Δ的正交中心。如果满足wp＞πz（p），则称为Δ和p点冲突（也可以将单纯形的正交中心理解为权为正交球半径平方的带权点，当该点与p点干涉时，单纯形和p点冲突）。在带权Delaunay三角化的结果中，将所有与p点冲突的单纯形从带权Delaunay三角化中删除，将形成一个空洞，称为带权Delaunay空洞，又称为Regular空洞（Regular Cavity）。
根据d维空间的带权Delaunay三角化与d+1维空间的凸包之间的关系，可以在d+1维空间的凸包CH（S+）上考察将p点加入带权Delaunay三角化中带权Delaunay空洞的形成过程：如果Δ=ΔT和p点冲突，意味着p+点在过ΔT+=CH（T+）的超平面的下方。在带权Delaunay三角化中，删除CH（S+）的所有p+在其下方的下部小面对应的单纯形，形成带权Delaunay空洞。
2.带权Delaunay空洞构造算法
带权Delaunay空洞构造算法的思路如下：带权Delaunay空洞构造算法是一种增量算法，S中的点是逐点加入、逐点处理的。与局部变换算法一样，需要选择一个初始的足够大的d-单纯形。设点集S={p1，p2，…，pn}，选择d+1的权为0的点构成点集S0={p-d，p-d+l，…，p0}，构造一个d-单纯形ΔS0=CH（S0）。选择的S0要保证ΔS0包含S中所有的点，并且保证WD（S）的每个d-单纯形是WD（S ∪ S0）的d-单纯形。
定义Si={p-d，p-d+1，…，pi}。给定R（Si-1），设Δ=ΔT是WD（Si-1）中包含pi点的d-单纯形。如果加入pi后，Δ仍然是正则的，则WD（Si）=WD（Si-1）。否则，删除Δ，并且根据邻接关系，删除Δ周围所有与pi冲突的d-单纯形，得到pi点的带权Delaunay空洞，并且将空洞多面体的每个小面的顶点和pi相连形成新的d-单纯形，从而得到WD（Si）。当点集S中所有的点处理完成后，将得到WD（S）。
算法：带权Delaunay空洞构造算法
{
1 构造WD（S0）=ΔS0
2 for i：=1 to n do
3 在WD（Si-1）中找到包含pi点的d-单纯形Δ
4 if WD（T ∪{pi}）≠ΔT then
删除Δ，并且根据邻接关系，删除Δ周围所有与pi冲突的d-单纯形，得到pi点的带权D elaunay空洞
6 while pi点的带权Delaunay空洞中存在未处理的小面do
7 得到一个未处理的小面，设其所有顶点组成的集合为U，生成新的d-单纯形ΔU ∪{pi}，在点集Si中是正则的，也就是说Δ属于W D（Si）设置新生成的d-单纯形之间的邻接关系，以及新的
地下水三维可视化系统开发与应用
Ⅳ 凸包的平面求法
这个算法是由数学大师葛立恒（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.
Ⅳ 程序员必须掌握哪些算法
一.基本算法:
枚举. (poj1753,poj2965)
贪心(poj1328,poj2109,poj2586)
递归和分治法.
递推.
构造法.(poj3295)
模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.图算法:
图的深度优先遍历和广度优先遍历.
最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
最小生成树算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
拓扑排序 (poj1094)
二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)
最大流的增广路算法(KM算法). (poj1459,poj3436)
三.数据结构.
串 (poj1035,poj3080,poj1936)
排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)
简单并查集的应用.
哈希表和二分查找等高效查找法(数的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
哈夫曼树(poj3253)
堆
trie树(静态建树、动态建树) (poj2513)
四.简单搜索
深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.动态规划
背包问题. (poj1837,poj1276)
型如下表的简单DP(可参考lrj的书 page149):
E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159)
C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)
六.数学
组合数学:
1.加法原理和乘法原理.
2.排列组合.
3.递推关系.
(POJ3252,poj1850,poj1019,poj1942)
数论.
1.素数与整除问题
2.进制位.
3.同余模运算.
(poj2635, poj3292,poj1845,poj2115)
计算方法.
1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)
七.计算几何学.
几何公式.
叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)
多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)
(poj1408,poj1584)
凸包. (poj2187,poj1113)
中级（校赛压轴及省赛中等难度）:
一.基本算法:
C++的标准模版库的应用. (poj3096,poj3007)
较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)
二.图算法:
差分约束系统的建立和求解. (poj1201,poj2983)
最小费用最大流(poj2516,poj2516,poj2195)
双连通分量(poj2942)
强连通分支及其缩点.(poj2186)
图的割边和割点(poj3352)
最小割模型、网络流规约(poj3308)
三.数据结构.
线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)
静态二叉检索树. (poj2482,poj2352)
树状树组(poj1195,poj3321)
RMQ. (poj3264,poj3368)
并查集的高级应用. (poj1703,2492)
KMP算法. (poj1961,poj2406)
四.搜索
最优化剪枝和可行性剪枝
搜索的技巧和优化 (poj3411,poj1724)
记忆化搜索(poj3373,poj1691)
五.动态规划
较为复杂的动态规划(如动态规划解特别的旅行商TSP问题等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
记录状态的动态规划. (POJ3254,poj2411,poj1185)
树型动态规划(poj2057,poj1947,poj2486,poj3140)
六.数学
组合数学:
1.容斥原理.
2.抽屉原理.
3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).
4.递推关系和母函数.
数学.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率问题. (poj3071,poj3440)
3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)
计算方法.
1.0/1分数规划. (poj2976)
2.三分法求解单峰(单谷)的极值.
3.矩阵法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
随机化算法(poj3318,poj2454)
杂题(poj1870,poj3296,poj3286,poj1095)
七.计算几何学.
坐标离散化.
扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用)
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
多边形的内核(半平面交)(poj3130,poj3335)
几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)
高级（regional中等难度）:
一.基本算法要求:
代码快速写成,精简但不失风格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
保证正确性和高效性. poj3434
二.图算法:
度限制最小生成树和第K最短路. (poj1639)
最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
最优比率生成树. (poj2728)
最小树形图(poj3164)
次小生成树.
无向图、有向图的最小环
三.数据结构.
trie图的建立和应用. (poj2778)
LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法(RMQ+dfs)).(poj1330)
双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的). (poj2823)
左偏树(可合并堆).
后缀树(非常有用的数据结构,也是赛区考题的热点).(poj3415,poj3294)
四.搜索
较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)
五.动态规划
需要用数据结构优化的动态规划.(poj2754,poj3378,poj3017)
四边形不等式理论.
较难的状态DP(poj3133)
六.数学
组合数学.
1.MoBius反演(poj2888,poj2154)
2.偏序关系理论.
博奕论.
1.极大极小过程(poj3317,poj1085)
2.Nim问题.
七.计算几何学.
半平面求交(poj3384,poj2540)
可视图的建立(poj2966)
点集最小圆覆盖.
对踵点(poj2079)
Ⅵ 周培德算法
平面点集三角剖分的周培德算法是周培德于1996提出的(周培德，1996，2000)，该算法首先对点集逐层求凸包，如图3.8(a)所示为需要剖分的点集，图3.8(b)为对点集逐层求凸包，对点集逐层求凸包时可能存在1个或2个孤立点无法组成凸包，此时恰好没有剩下孤立的点;然后将两两凸包之间的环状区域分割成三角形，最后调整相邻环域的三角剖分便能获得最小权的三角剖分，如图3.8(c)为从内到外将凸包之间的环状区域分割成三角形，图3.8(d)为点集的三角剖分结果。
第十三步:对以Cm中的边(或已变动的边)为共用边的三角形对，采用第十二步的方法检查是否需要改变原有的三角剖分。然后，沿Cm-1，…，C2的各条边(或已变动的边)寻找两个有共用边的三角形对，并用第十二步的方法检查是否需要改变原来的三角剖分，直到所有凸壳的边检查完为止。
Ⅶ matlab如何求大量数据中分布最多的范围及中心点。
楼主是不是想求出一个最小半径的圆，圆内包含所有的点？这个问题很有趣。
寻找这个圆的时候注意一下几点：
1.这个圆必然穿过图中某些靠外围的点，这样才是最小半径的圆。
2.几何中我们知道，三个点可以确定一个圆, 我们就是需要找出这三个点来.
算法如下：1.先求这些点对应的凸包，已经有现成的算法。
2.生成凸包后，在看凸包上哪三点确定的圆可以包含凸包。
当然如果楼主讨论的不是以上所述，而是模式分类的话，建议看看数据分类方法。可以搜索关键字：Gaussian mixtrual model, expectation-maximization algorithm 和 k-mean algorithm 学习下相关的知识。
Ⅷ 挑战程序设计竞赛（第2版）的目录
《挑战程序设计竞赛(第2版)》
第1章蓄势待发——准备篇1 1.1 何谓程序设计竞赛2 1.2 最负盛名的程序设计竞赛5 1.2.1 世界规模的大赛——google code jam（gcj）5 1.2.2 向高排名看齐！——topcoder5 1.2.3 历史最悠久的竞赛—— acm-icpc6 1.2.4 面向中学生的信息学奥林匹克竞赛——joi-ioi6 1.2.5 通过网络自动评测——online judge（oj）6 1.3 本书的使用方法7 1.3.1 本书所涉及的内容7 1.3.2 所用的编程语言7 1.3.3 题目描述的处理7 1.3.4 程序结构7 1.3.5 练习题8 1.3.6 读透本书后更上一层楼的练习方法8 1.4 如何提交解答9 1.4.1 poj的提交方法9 1.4.2 gcj的提交方法11 1.5 以高效的算法为目标15
.1.5.1 什么是复杂度15 1.5.2 关于运行时间15 1.6 轻松热身16 1.6.1 先从简单题开始16 1.6.2 poj的题目ants18 1.6.3 难度增加的抽签问题20 第2章初出茅庐——初级篇25 2.1 最基础的“穷竭搜索”26 2.1.1 递归函数26 2.1.2 栈27 2.1.3 队列28 2.1.4 深度优先搜索29 2.1.5 宽度优先搜索33 2.1.6 特殊状态的枚举37 2.1.7 剪枝38 2.2 一往直前！贪心法39 2.2.1 硬币问题39 2.2.2 区间问题40 2.2.3 字典序最小问题43 2.2.4 其他例题45 2.3 记录结果再利用的“动态规划”51 2.3.1 记忆化搜索与动态规划51 2.3.2 进一步探讨递推关系57 2.3.3 有关计数问题的dp66 2.4 加工并存储数据的数据结构70 2.4.1 树和二叉树70 2.4.2 优先队列和堆71 2.4.3 二叉搜索树77 2.4.4 并查集84 2.5 它们其实都是“图”91 2.5.1 图是什么91 2.5.2 图的表示94 2.5.3 图的搜索97 2.5.4 最短路问题99 2.5.5 最小生成树105 2.5.6 应用问题107 2.6 数学问题的解题窍门113 2.6.1 辗转相除法113 2.6.2 有关素数的基础算法117 2.6.3 模运算121 2.6.4 快速幂运算122 2.7 一起来挑战gcj的题目（1）125 2.7.1 minimum scalar proct125 2.7.2 crazy rows127 2.7.3 bribe the prisoners129 2.7.4 millionaire132 第3章出类拔萃——中级篇137 3.1 不光是查找值！“二分搜索”138 3.1.1 从有序数组中查找某个值138 3.1.2 假定一个解并判断是否可行140 3.1.3 最大化最小值142 3.1.4 最大化平均值143 3.2 常用技巧精选（一）146 3.2.1 尺取法146 3.2.2 反转（开关问题）150 3.2.3 弹性碰撞158 3.2.4 折半枚举（双向搜索）160 3.2.5 坐标离散化164 3.3 活用各种数据结构167 3.3.1 线段树167 3.3.2 binary indexed tree174 3.3.3 分桶法和平方分割183 3.4 熟练掌握动态规划191 3.4.1 状态压缩dp191 3.4.2 矩阵的幂199 3.4.3 利用数据结构高效求解206 3.5 借助水流解决问题的网络流209 3.5.1 最大流209 3.5.2 最小割212 3.5.3 二分图匹配217 3.5.4 一般图匹配220 3.5.5 匹配、边覆盖、独立集和顶点覆盖221 3.5.6 最小费用流222 3.5.7 应用问题228 3.6 与平面和空间打交道的计算几何250 3.6.1 计算几何基础250 3.6.2 极限情况255 3.6.3 平面扫描258 3.6.4 凸包260 3.6.5 数值积分263 3.7 一起来挑战gcj的题目（2）267 3.7.1 numbers267 3.7.2 no cheating269 3.7.3 stock charts271 3.7.4 watering plants273 3.7.5 number sets278 3.7.6 wi-fi towers280 第4章登峰造极——高级篇285 4.1 更加复杂的数学问题286 4.1.1 矩阵286 4.1.2 模运算的世界291 4.1.3 计数295 4.1.4 具有对称性的计数300 4.2 找出游戏的必胜策略305 4.2.1 游戏与必胜策略305 4.2.2 nim311 4.2.3 grundy数315 4.3 成为图论大师之路320 4.3.1 强连通分量分解320 4.3.2 2-sat324 4.3.3 lca328 4.4 常用技巧精选（二）335 4.4.1 栈的运用335 4.4.2 双端队列的运用337 4.4.3 倍增法345 4.5 开动脑筋智慧搜索350 4.5.1 剪枝350 4.5.2 a*与ida*356 4.6 划分、解决、合并：分治法359 4.6.1 数列上的分治法359 4.6.2 树上的分治法360 4.6.3 平面上的分治法364 4.7 华丽地处理字符串368 4.7.1 字符串上的动态规划算法368 4.7.2 字符串匹配373 4.7.3 后缀数组378 4.8 一起来挑战gcj的题目（3）387 4.8.1 mine layer387 4.8.2 year of more code jam392 4.8.3 football team395 4.8.4 endless knight399 4.8.5 the year of code jam403 本书中未涉及的拓展主题408 书中例题列表411 参考文献413
Ⅸ Bezier曲线定义与性质，分别给出算法简述。
一、Bezier曲线定义：
给定n+1个控制顶点Pi(i=0~n) ，则Bezier曲线定义为：
P(t)=∑Bi,n(t)Pi u∈[0,1]
其中：Bi,n(t)称为基函数。
Bi,n(t)=Ci nti (1-t)n-i
Ci n=n!/(i!*(n-i)!)
二、Bezier曲线性质
1、端点性质：
a）P(0)=P0, P(1)=Pn, 即：曲线过二端点。
b）P’(0)=n(P1-P0), P’(1)=n(Pn-Pn-1)
即：在二端点与控制多边形相切。
2、凸包性：Bezier曲线完成落在控制多边形的凸包内。
3、对称性：由Pi与Pn-i组成的曲线，位置一致，方向相反。
4、包络性：Pn (t)=(1-t)Pn-1 (t)+tPn-1 (t)