模板：二维凸包（计算几何）

所谓凸包，就是一个凸出来的包

（逃）

解析集合的第一课。
关键特征：周长最小。此时一定是凸包。

凸包：在平面上能包含所有给定点的最小凸多边形叫做凸包。

性质：凸包的周长是所有能包含给定点的多边形中最小的。

凸包的主流求法有 Andrew 和 Graham，两者的复杂度瓶颈都在于排序，为 O ( n log ⁡ n ) O(nlog n) O(nlogn)。
这里介绍较为简单的 Graham 扫描法。

首先，找出所有点中按照 X − Y X-Y X−Y 排序最小的点 O O O。
然后以 O O O 作为原点，把所有其它点按照极角排序，极角相同时按距离升序排序（实测这里也可以降序，但是绝对不能无序）。
可以用快排重载 cmp 函数的方法实现，利用叉积判断。

bool cmp(V a,V b){
	double d=(a-p[1])^(b-p[1]);
	if(abs(d)>eps) return d>0;
	else return len(a-p[1]) 
排好序后，开一个栈维护当前凸包中的点。
 如果新点破坏了凸性，则不断退栈。
 最终栈内的元素就是凸包中的点。
 
是否破坏凸性可以用叉积判断，如果新点和栈顶形成的向量向右拐了（叉积小于0），则说明破坏了凸性。
 
 
 
注意：这里判断退栈的条件最好带等！，一方面，共线时在边上的顶点没有什么意义，另一方面，当有重合点时，不带等会导致程序错误。
 
 
void ConvexHull(V *p,int &n){
	int top=0;
	sort(p+1,p+1+n);
	sort(p+2,p+1+n,cmp);
	top=0;
	for(int i=1;i<=n;i++){
		while((top>1&&((zhan[top]-zhan[top-1])^(p[i]-zhan[top]))<=0)) --top;
		zhan[++top]=p[i];
	}
	memcpy(p,zhan,sizeof(zhan));
	n=top;
	return;
}
 
完整代码 
P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包
 
#include
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
inline ll read(){
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
  while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}

//basic declare
//#define double long double
const double eps=1e-10;
const double pi=acos(-1.0);

//---about vectors (or points)

//definition
struct V{
  double x,y;
  V():x(0),y(0){}
  V(double a,double b):x(a),y(b){}
};
V ans[10];//declared for other functions
int tot;
inline void input(V &a){scanf("%lf%lf",&a.x,&a.y);}
void print(const V &a,int op=1){printf("%.10lf %.10lf",a.x,a.y);putchar(op?10:32);}
//op:endl or space

//basic operation
inline V operator + (const V &a,const V &b){return (V){a.x+b.x,a.y+b.y};}
inline V operator - (const V &a,const V &b){return (V){a.x-b.x,a.y-b.y};}
inline V operator * (const double &x,const V &a){return (V){a.x*x,a.y*x};}
inline V operator * (const V &a,const double &x){return (V){a.x*x,a.y*x};}
inline V operator / (const V &a,const double x){return (V){a.x/x,a.y/x};}
inline bool operator == (const V &a,const V &b){return abs(a.x-b.x)eps) return d>0;
	else return len(a-p[1])1&&((zhan[top]-zhan[top-1])^(p[i]-zhan[top]))<=0)) --top;
		zhan[++top]=p[i];
	}
	memcpy(p,zhan,sizeof(zhan));
	n=top;
	return;
}
signed main(){
#ifndef ONLINE_JUDGE
  //freopen("a.in","r",stdin);
  //freopen("a.out","w",stdout);
#endif
  n=read();
  for(int i=1;i<=n;i++) input(p[i]);
  ConvexHull(p,n);
  zhan[n+1]=p[1];
  double res(0);
  for(int i=1;i<=n;i++) res+=len(zhan[i+1]-zhan[i]);//print(zhan[i]);
  printf("%.2lfn",res);
  return 0;
}




					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5691315.html