改革春风吹满地

 HDU - 2036 

“ 改革春风吹满地, 
不会AC没关系; 
实在不行回老家， 
还有一亩三分地。 
谢谢!（乐队奏乐）” 

话说部分学生心态极好，每天就知道游戏，这次考试如此简单的题目，也是云里雾里，而且，还竟然来这么几句打油诗。 
好呀，老师的责任就是帮你解决问题，既然想种田，那就分你一块。 
这块田位于浙江省温州市苍南县灵溪镇林家铺子村，多边形形状的一块地，原本是linle 的，现在就准备送给你了。不过，任何事情都没有那么简单，你必须首先告诉我这块地到底有多少面积，如果回答正确才能真正得到这块地。 
发愁了吧？就是要让你知道，种地也是需要AC知识的！以后还是好好练吧... 

Input

输入数据包含多个测试实例，每个测试实例占一行，每行的开始是一个整数n(3<=n<=100)，它表示多边形的边数（当然也是顶点数），然后是按照逆时针顺序给出的n个顶点的坐标（x1, y1, x2, y2... xn, yn）,为了简化问题，这里的所有坐标都用整数表示。 
输入数据中所有的整数都在32位整数范围内，n=0表示数据的结束，不做处理。 

Output

对于每个测试实例，请输出对应的多边形面积，结果精确到小数点后一位小数。 
每个实例的输出占一行。 

Sample Input

3 0 0 1 0 0 1
4 1 0 0 1 -1 0 0 -1
0

Sample Output

0.5
2.0

任意多边形面积 求解思路：

要想求任意多边形面积则可将任意三点相连，将多面形面分成若干个三角形面积和。

之后求出每个三角形面积，相加求解。

在 已知点坐标 的情况下，求三角形面积有经常有以下两种方法。

1.）海伦公式：

有一个三角形，边长分别为a、b、c，三角形的面积S可由以下公式求得：S=√[p(p-a)(p-b)(p-c)] 而公式里的p为半周长： 

                                                                               p=(a+b+c)/2

但是一般不会选用这种方法，因为 1：计算量大。2：精度损失。

2.）利用向量的叉乘（向量积）求面积

设一三角形三点坐标：A(x1, y1), B(x2, y2), C(x3, y3)，则面积的行列式形式如下：

按第三列展开：

这样求出一个三角形的有向面积。

而在叉乘的性质：设两向量P和Q 

* 1.P ×Q > 0 则Q在P的逆时针方向 

* 2.P ×Q < 0 则Q在P的顺时针方向

* 3.P ×Q = 0 则Q和P共线，方向可能相同也可能不相同 

所以，由三角形三点的顺逆时针顺序而判断出叉乘正负：

点如果是顺时针给出，有向面积为负（求面积时，为叉乘求得有向面积的相反数），逆时针给出，有向面积为正。

如图所示，∆ABC有向面积>0、∆ABD有向面积<0. 

所以当求多边形面积（凹多边形也适用）时，可将图形划分为多个三角形，并将其有向面积相加（若是凹多边形，则多算的面积所求的的有向面积为负，相加时正好减去）。

当三角形公共点在多边形内时

经过以上分析，给出任意一个多边形，其顶点坐标依次为（x0，y0），（x1，y1），（x2，y2），...，（xn，yn）（其中n=2，3，4，…），则其面积可表示为：

当公共点在多边形外时（一般选为原点）

如果我们不以多边形的某一点为顶点来划分三角形而是以任意一点，如下图，这个方法也是成立的：S = S_OAB + S_OBC + S_OCD + S_ODE + S_OEA。计算的时候，当我们取O点为原点时，可以简化计算。                     

当O点为原点时，根据向量的叉积计算公式，各个三角形的面积计算如下：

S_OAB = 0.5*(A_x*B_y - A_y*B_x)   【(A_x，A_y)为A点的坐标】

S_OBC = 0.5*(B_x*C_y - B_y*C_x)

S_OCD = 0.5*(C_x*D_y - C_y*D_x)

S_ODE = 0.5*(D_x*E_y - D_y*E_x)

S_OEA = 0.5*(E_x*A_y - E_y*A_x)

S_总= S_  相加之和

本题题解

#include <bits/stdc++.h>
using namespace std;

struct zuobiao {
	int x,y;
};

int main (){
	int a;
	while(scanf("%d",&a)!=EOF){
		if(a==0)break;
	zuobiao p[a];
	int i;
	for(i=0;i<a;i++){
		cin>>p[i].x;
		cin>>p[i].y;
	//	cout<<p[a].x<<p[a].y;
	}
	double area=0;
	for(i=0;i<a-1;i++) {
		area+=(p[i].x*p[i+1].y-p[i+1].x*p[i].y);
	}
	printf("%.1lf\n",0.5*(area-p[0].x*p[a-1].y+p[a-1].x*p[0].y));
	}
	return 0;
}