HDU2036 多边形面积模板

利用向量叉乘:三角形ABC面积可以利用向量  (↑AB) ×(↑AC)*(1/2)得出,对于多边形,可以随意选取多边形某一点为源点然后一次计算.对于如下:

的多边形

我们可以以P1为扇面中心，连接P1Pi就得到N-2个三角形，由于凸性，保证这些三角形全在多边形内，那么，这个凸多边形的有向面积：

     A=sigma(Ai)  (i=1…N-2)

[cpp] view plain copy print?

1. #include <stdio.h>  
2. #include <math.h>  
3. typedef struct node  
4. {  
5.     double x,y;  
6. }node;  
7. node s[1001];  
8.   
9. double cal(node x,node y,node z)  
10. {  
11.     return (y.x-x.x)*(z.y-x.y)-(y.y-x.y)*(z.x-x.x);  
12. }  
13. int main()  
14. {  
15.     int n,i;  
16.     double res;  
17.     while(scanf("%d",&n)&&n)  
18.     {  
19.         res=0;  
20.         for(i=0;i<n;i++)  
21.             scanf("%lf%lf",&s[i].x,&s[i].y);  
22.         for(i=1;i<n-1;i++)  
23.             res+=cal(s[0],s[i],s[i+1]);  
24.         printf("%.1lf\n",res/2.0);  
25.     }  
26.     return 0;  
27. }  

#include <stdio.h>
#include <math.h>
typedef struct node
{
	double x,y;
}node;
node s[1001];

double cal(node x,node y,node z)
{
	return (y.x-x.x)*(z.y-x.y)-(y.y-x.y)*(z.x-x.x);
}
int main()
{
	int n,i;
	double res;
	while(scanf("%d",&n)&&n)
	{
		res=0;
		for(i=0;i<n;i++)
			scanf("%lf%lf",&s[i].x,&s[i].y);
		for(i=1;i<n-1;i++)
			res+=cal(s[0],s[i],s[i+1]);
		printf("%.1lf\n",res/2.0);
	}
	return 0;
}