ZOJ 3194 Coverage（贪心）

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int MN=1100;
double x[MN],y[MN],r[MN];

bool cmp(double a,double b)
{
    return a<b;
}

int main()
{
    int i,j,n;
    double sum;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        sum=0;
        scanf("%d",&n);
        for(i=0;i<n;i++)
           scanf("%lf%lf",&x[i],&y[i]);
        sort(x,x+n,cmp);
        sort(y,y+n,cmp);
        for(i=0;i<n-1;i++)
        {
            if(i==0) r[i]=x[i+1]-x[i];
            else r[i]=x[i+1]-x[i-1];
        }
        r[i]=x[i]-x[i-1];
        sort(r,r+n,cmp);
        for(i=0;i<n;i++)
        {
            sum+=r[i]*y[i];
        }
        printf("%.1lf\n",sum/2);
    }
    return 0;
}