Description

好消息！南邮规划建设自行车停放场，现已选定多个场地，它们均为规则多边形。现请你帮助学校确定哪块场地面积最大，这里以鼎山之顶为平面坐标原点，按顺时针或逆时针给出顶点坐标。

Input

输入数据中含有一些多边形场地（1≤数量≤20），按输入顺序编号（从1开始）。每个多边形场地的第一行数据n（3≤n≤10），后续n行分别给出顶点的平面坐标（平面两个坐标的绝对值≤50）。

Output

输出面积最大的多边形场地序号。当面积最大的多边形场地有多个时，输出这些场地中的最小序号

Sample Input

2
3
0 0
0 1
1 0
4
0 0
0 1
1 1
1 0

Sample Output

2

Source

“IBM南邮杯”个人赛2009

分析：用了模板。模板写的真好！

附：多边形面积求法：

方法一：三角形法（最常用）
基本思想为： 
    把有n个顶点的多边形分成n个三角形，分别求得面积后求和，即得到多边形的面积。 
具体操作如下： 
   设多边形的顶点为P1,P2,...,Pn；另任取一点P0，与上述顶点组成n个三角形P0P1P2,   P0P2P3,   ...P0Pn-1Pn,P0PnP1。分别求得这n个三角形的面积为S1,S2,...,Sn;则多变形的面积为S=S1+S2+...+Sn 
为了简化计算，可以将多边形的某个点定义为P0；
三角形的面积公式： 
   设三角形的三个顶点的坐标为(x1,y1),(x2,y2),(x3,y3);   三角形的面积为s;则有如下公式成立 


        |   1   x1   y1   | 

 2s=  |   1   x2   y2   |        

        |   1   x3   y3   |

struct Point // 点结构体
{ 
	int x, y;
};

// 点的叉积: AB * AC
int cross(const Point &A, const Point &B, const Point &C) 
{
	return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

/*
* 计算多边形面积
* 参数：n个顶点， 多边形顶点坐标集合
*/
double polygon_area(const int &n, Point p[])
{
	double area = 0.0;
	int i;
	Point temp;

	temp.x = temp.y = 0; // 原点
	for (i = 0; i < n-1; ++i){
		area += cross(temp, p[i], p[i+1]);
	}
	area += cross(temp, p[n-1], p[0]); // 首尾相连
	area = area/2.0;        // 注意要除以2
	return area > 0 ? area : -area;    // 返回非负数
}

方法二：积分法（要考虑分段积分，复杂）
现在要求的多边形是由线段组成的，只要把所有的线段都求定积分，最后把和加起来，
就是多边形的面积。
这个推论的证明从略。值得注意的是，用定积分求的面积有正负之分，即：
b         a
∫f(x)dx=-∫f(x)dx
a         b
从a积到b，与从b积到a只相差一个负号。


　　线段定积分的计算公式的推导


给出两个点，如何求这两点连成的线段的定积分值呢？
直线的方程可以用y=kx+b表示，所以围成的面积
S=

x2
∫(kx+b)dx = k/2(x2^2-x1^2)+b(x2-x1) 
x1

而斜率k=(y2-y1)/(x2-x1)
截距b=y1-kx1=y1-x1(y2-y1)/(x2-x1)，代入前式得
S=(y2-y1)(x2+x1)/2+y1(x2-x1)-x1(y2-y1)
=(x2-x1)(y1+y2)/2
方法三：边长计算方法
也是拆分成三角形，只是三角形的计算方法用三边距离公式：
三角形的面积求法是S=sqr(p*(p-a)*(p-b)*(p-c)),其中，p=(a+b+c)/2,a、b、c为边长，a=sqr((x1-x2)^2+(y1-y2)^2) 

此题完整代码：（模板）

#include<iostream>
#include<cmath> // !!!
#include<string>
using namespace std;

//南邮仙林自行车停放场

struct POLY // 多边形，顺时针或逆时针给出x，y
{
	int n;
	double * x;
	double * y;
	POLY() : n(0), x(NULL), y(NULL) {}; // 无参构造
	POLY(int _n_ , const double * _x_, const double * _y_) // 带参构造
	{
		n = _n_;
		x = new double[n + 1];
		memcpy(x, _x_, n * sizeof(double));
		x[n] = _x_[0]; // 首尾要重合
		y = new double[n + 1];
		memcpy(y, _y_, n * sizeof(double));
		y[n] = _y_[0];
	}
};
double Area(const POLY & poly) // 求多边形面积
{
	if(poly.n < 3) return double(0);
	double s = poly.y[0] * (poly.x[poly.n - 1] - poly.x[1]);
	for(int i=1;i<poly.n;i++)
		s += poly.y[i] * (poly.x[i - 1] - poly.x[(i + 1) % poly.n]);
	return fabs(s/2); // 会有负数
}

int main()
{
	int N;
	POLY poly[21];
	double area[21];
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	{
		int n; // 几个点
		double x[10];
		double y[10];
		scanf("%d",&n);
		for(int i=0;i<n;i++)
			scanf("%lf%lf",&x[i],&y[i]);
		poly[i] = POLY(n, x, y);
		area[i] = Area(poly[i]);
	}
	double max = 0.0;
	int number;
	for(int i=1;i<=N;i++)
	{
		//	printf("%f ",area[i]);
		if(max < area[i])
		{
			max = area[i];
			number = i;
		}
	}
	printf("%d\n",number);
	return 0;
}

另一种简便的写法：

#include<iostream>
#include<cmath>
using namespace std;

struct Point
{double x, y;};

double area_polygon(int n, Point *p)
{
	double s1 = 0, s2 = 0;
	for(int i=0;i<n;i++)
		s1 += p[(i+1)%n].y * p[i].x, s2 +=  p[(i+1)%n].y * p[(i+2)%n].x; // 还能这样写！！！
	return fabs(s1 - s2) / 2;
}

int main()
{
	int ncases, n, max = -1;
	double s, maxs = -1;
	cin>>ncases;
	for(int i=0;i<ncases;i++)
	{
		cin>>n;
		double x, y;
		Point *p = new Point[n];
		for(int j=0;j<n;j++)
		{
			cin>>x>>y;
			p[j].x = x;
			p[j].y = y;
		}
		s = area_polygon(n, p);
		if(maxs < s)
		{
			max = i;
			maxs = s;
		}
	}
	cout<<max+1;

	return 0;
}