转载自：http://www.cnblogs.com/hate13/p/4160751.html
Max Area
题目描述：(链接：http://acm.swust.edu.cn/problem/24/)
又是这道题，请不要惊讶，也许你已经见过了，那就请你再来做一遍吧。这可是wolf最骄傲的题目哦。
在笛卡尔坐标系正半轴（x>=0,y>=0）上有n个点，给出了这些点的横坐标和纵坐标，但麻烦的是这些点的坐标没有配对好，你的任务就是将这n个点的横坐标和纵坐标配对好，使得这n个点与x轴围成的面积最大。
输入：
在数据的第一行有一个正整数m,表示有m组测试实例。接下来有m行，每行表示一组测试实例。每行的第一个数n，表示给出了n个点，接着给出了n个x坐标和y坐标。（给出的x轴的数据不会重复，y轴数据也不会重复）（m<5000,1<n<50）
如：
2
4 x1 x2 x3 x4 y1 y2 y3 y4
5 x1 x2 x3 x4 x5 y1 y2 y3 y4 y5
输出：
输出所计算的最大面积，结果保留两位小数，每组数据占一行。
样例：
2
4 0 1 3 5 1 2 3 4
6 14 0 5 4 6 8 1 5 6 2 4 3
15.00
59.00
简单贪心、输入数据应该为double、Wa一次。
思路：画图、整个多边形面积可以划分为n-1个直角梯形的面积之和、将n个x坐标（或y坐标）看做n-1个高，然后面积等于所有（上底+下底）*高/2的和。
这里直接处理不好处理，展开、然后除了两边、中间的每个底需要乘以相邻两个高，故如样例1：
则S=（y1*h1 + y2+(h1+h2) + y3*(h2+h3) + y4*h3）/2，y表示纵坐标，即底，h为高。然后排序贪心即可。
好吧、没说清楚、画下图就知道了。
代码如下：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define N 5010 int n;
double x[N];
double y[N];
double h[N]; void solve()
{
int i,j;
sort(x+,x+n+);
for(i=;i<=n;i++)
{
if(i==) h[i]=x[i+]-x[i];
else if(i==n) h[i]=x[i]-x[i-];
else h[i]=x[i+]-x[i-];
}
sort(h+,h+n+);
sort(y+,y+n+);
double ans=;
for(i=;i<=n;i++)
{
ans+=h[i]*y[i];
}
printf("%.2f\n",ans/2.0);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%lf",&x[i]);
for(int i=;i<=n;i++) scanf("%lf",&y[i]);
solve();
}
return ;
}