凸包算法(二)--凸包面积

凸包面积算法

1.选取p0作为y坐标最小的点，如果y坐标相等，选取x坐标最小的点

2.对剩余的点相对与p0点的极角进行排序

（比较叉积<http://blog.csdn.net/liufei_learning/archive/2010/10/14/5941947.aspx> ）

3.去除极角相等的点，即距离最远的点

4.初始化堆栈

5.折线段拐向判断，若没有左转的时候出栈点，否则入栈

6.根据已有的点计算面积

凸包面积

Time Limit: 1000MS Memory Limit: 65536KB

Submissions: 38 Accepted: 10

Description

麦兜是个淘气的孩子。一天，他在玩钢笔的时候把墨水洒在了白色的墙上。再过一会，麦兜妈就要回来了，麦兜为了不让妈妈知道这件事情，就想用一个白色的凸多边形把墙上的墨点盖住。你能告诉麦兜最小需要面积多大的凸多边形才能把这些墨点盖住吗？现在，给出了这些墨点的坐标，请帮助麦兜计算出覆盖这些墨点的最小凸多边形的面积。

Input

多组测试数据。第一行是一个整数T，表明一共有T组测试数据。每组测试数据的第一行是一个正整数N(0< N < = 105)，表明了墨点的数量。接下来的N行每行包含了两个整数Xi和Yi（0<=Xi,Yi<=2000），表示每个墨点的坐标。每行的坐标间可能包含多个空格。

Output

每行输出一组测试数据的结果，只需输出最小凸多边形的面积。面积是个实数，小数点后面保留一位即可，不需要多余的空格。

Sample Input

2

4

0 0

1 0

0 1

1 1

2

0 0

0 1Sample Output

1.0

0.0

Hint

Source

#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;

struct Vertex
{
	int x;
	int y;
};
Vertex ver[107];

//根据叉积排序极角，当极角相等时距离远的点在前面，方便后面删除极角一样的点
bool cmp(Vertex ver1, Vertex ver2)
{
	int x1,x2,y1,y2,s;
	x1 = ver1.x-ver[0].x;
	y1 = ver1.y-ver[0].y;
	x2 = ver2.x-ver[0].x;
	y2 = ver2.y-ver[0].y;
	s = x1*y2 - x2*y1;
	if(s>0 || s==0 && x1*x1+y1*y1>x2*x2+y2*y2)
		return true;
	else
		return false;
}

//线段拐向的判断
//若(p2 - p0) × (p1 - p0) > 0,则p0p1在p1点拐向右侧后得到p1p2。
//若(p2 - p0) × (p1 - p0) < 0,则p0p1在p1点拐向左侧后得到p1p2。
//若(p2 - p0) × (p1 - p0) = 0,则p0、p1、p2三点共线
inline int dig(int x0, int y0, int x1, int y1, int x2, int y2)
{
	return (x2 - x0) * (y1 - y0) - (y2 - y0) * (x1 - x0);
}

//交换
void Swap(Vertex &ver1, Vertex &ver2)
{
	Vertex temp;
	temp.x = ver1.x;
	temp.y = ver1.y;
	ver1.x = ver2.x;
	ver1.y = ver2.y;
	ver2.x = temp.x;
	ver2.y = temp.y;
}

int main()
{
	double s,m;
	int t,p,n,i,j,k,a,b;
	int StackVer[107];
	int pVer;
	int MinY;
	cin>>t;
	for (p=0; p<t; p++)
	{
		cin>>n;
		for (i=0; i<n; i++)
			cin>>ver[i].x>>ver[i].y;
		if(n<=2) 
		{
			cout<<"0.0"<<endl;
			continue;
		}
		s=0;
		pVer=0;
		MinY = 0;
		for (i=1; i<n; i++)
		{
			if (ver[i].y<ver[MinY].y || ver[i].y==ver[MinY].y&&ver[i].x<ver[MinY].x)
			{
				MinY = i;
			}
		}
		
		Swap(ver[0],ver[MinY]);
		sort(ver+1,ver+n, cmp);
		k=2;
		//删除重复的点
		for(i=2; i<n; i++)
		{
			if(dig(ver[0].x, ver[0].y, ver[i-1].x,ver[i-1].y, ver[i].x, ver[i].y) != 0)
				ver[k++] = ver[i];
		}
		//堆栈初始化
		StackVer[pVer++] = 0;
		StackVer[pVer++] = 1;
		StackVer[pVer++] = 2;
		
		//找到所有极点
		 for(i = 3; i < k; i++) 
		 {
				for(a = StackVer[pVer - 2], b = StackVer[pVer - 1];
				 ! (dig(ver[a].x, ver[a].y, ver[b].x, ver[b].y, ver[i].x, ver[i].y)< 0);
				  a = StackVer[pVer - 2], b = StackVer[pVer - 1]) 
				  {
					  pVer--;   //删点
				  }
				  StackVer[pVer++] = i;  //加点
		}
		
		//计算面积
		while(pVer>=2)
		{
			a = StackVer[pVer - 2];
			b = StackVer[pVer - 1];
			m = dig( ver[0].x, ver[0].y,ver[b].x, ver[b].y,ver[a].x, ver[a].y)/2.0;
			if(m<0) m=-m;
			pVer--;
			s=s+m;
		}
		cout<<setiosflags(ios::fixed)<<setprecision(1)<<s<<endl;	
	}
	return 0;
}

PKU1873TheFortifiedForest(枚举+凸包）
题意：
有n棵树(2<=n<=15)，每棵树有四个特征量(x[i], y[i], v[i], l[i]),(1 <= i <= n)其中（x[i], y[i])是该树在平面上的位置，v[i]为该树价值，l[i]为该树的树高，现在要求砍掉一些树来做围栏，
把剩下的树围起来，要求砍掉的树的价值和minValue最小，当minValue不唯一时，要求砍掉的树的数目最少？
思路：枚举 + 凸包
源代码：
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 15;
const double eps = 1e-7;
struct Tpoint {
 int x, y;
};
Tpoint point[MAXN], p[MAXN];
int nn, n, num, ans_cnt, cost, lstack, minimum;
int mark[MAXN], stack[MAXN], ans[MAXN], l[MAXN],v[MAXN];
double ans_extra;
inline int det(int x0, int y0, int x1, int y1, int x2, int y2) //计算叉积
{
 return (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0);
}
inline int det(int x1, int y1, int x2, int y2) //计算叉积
{
 return x1 * y2 - x2 * y1;
}
bool cmp(Tpoint a, Tpoint b) //极角比较
{
 int a1 = a.x - point[0].x, b1 = a.y - point[0].y;
 int a2 = b.x - point[0].x, b2 = b.y - point[0].y;
 int p = det(a1, b1, a2, b2);
 return p > 0 || (p == 0 && a1 * a1 + b1 * b1 > a2 * a2 + b2 * b2);
}
inline double dist(Tpoint a,Tpoint b) //计算距离
{
 return sqrt((double)((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)));
}
void init_convex() //初始化凸包
{
 int i, mn = 0; //min
 for(i = 1; i < nn; i ++) { //求最低点
 if((point[i].y < point[mn].y) ||
 (point[i].y == point[mn].y && point[i].x < point[mn].x))
 mn = i;
 }
 swap(point[0],point[mn]);
 sort(point + 1, point + nn, cmp); //求极角序
 num = 2;
 for(i = 2; i < nn; i ++) { //去掉极角重复的点
 if(det(point[0].x, point[0].y, point[i-1].x,
 point[i-1].y, point[i].x, point[i].y) != 0)
 point[num ++] = point[i];
 }
}
void convex() //求凸包
{
 int i, a, b;
 lstack = 0;
 stack[lstack ++] = 0;
 stack[lstack ++] = 1;
 stack[lstack ++] = 2;
 for(i = 3; i < num; i ++) {
 for(a = stack[lstack - 2], b = stack[lstack - 1]; //求凸性
 det(point[a].x, point[a].y, point[b].x,
 point[b].y, point[i].x, point[i].y) <= 0;
 a = stack[lstack - 2], b = stack[lstack - 1]) {
 lstack --; //删点
 }
 stack[lstack++] = i; //加点
 }
}

void proc()
{
 nn = 0;
 int i, tot = 0;
 for(i = 0; i < n; i ++) {
 if(! mark[i]) point[nn ++] = p[i];
 else tot += l[i];
 }
 if(nn > 2) {
 init_convex();
 convex();
 }else { //特殊情况
 lstack = nn;
 for(i = 0; i < nn; i ++) stack[i] = i;
 }
 stack[lstack] = stack[0];
 double now = 0;
 for(i = 0; i < lstack; i ++) {
 now += dist(point[stack[i]], point[stack[i + 1]]);
 }
 if(now <= tot + eps) { //方案合法，更新最优解
 if((cost == minimum && n - nn < ans_cnt) || (cost < minimum)) {
 minimum = cost;
 ans_cnt = 0;
 for(i = 0; i < n; i ++) {
 if(mark[i]) ans[ans_cnt ++] = i;
 }
 ans_extra = tot - now;
 }
 }
}
void dfs(int k)
{
 if(k == n) {
 if(cost <= minimum) proc();
 }else {
 dfs(k + 1);
 mark[k] = 1;
 cost += v[k];
 dfs(k + 1);
 cost -= v[k];
 mark[k] = 0;
 }
}
int main()
{
 int i, cases = 0;
 while(scanf("%d", &n) && n) {
 for(i = 0; i < n; i ++)
 scanf("%d %d %d %d", &p[i].x, &p[i].y, &v[i], &l[i]);
 memset(mark, 0, sizeof(mark));
 minimum = INT_MAX;
 cost = 0;
 dfs(0);
 printf("Forest %d/n",++cases);
 printf("Cut these trees:");
 for(i = 0; i < ans_cnt; i ++)
 printf(" %d", ans[i] + 1);
 printf("/nExtra wood: %.2lf/n/n", ans_extra);
 }
 return(0);
}

源文档 <http://blog.sina.com.cn/s/blog_5c95cb070100d9t8.html>