POJ 1389 Area of Simple Polygons （离散化求矩形面积并）

题意：在二维平面上给出n个矩形的坐标，矩形的边与x轴和y轴平行，求这n个矩形覆盖的面积。

数据范围：n<=1000, x,y均为不大于50000的正整数

分析：由于坐标都是整数的，我们可以把二维平面看成由面积都是1的小方格组成，最暴力的方法就是标记每个矩形覆盖的小方格，最后再统计一共有多少小方格被覆盖，但是坐标平面太大了，最坏情况下为50000*50000，肯定超时了。虽然坐标范围比较大，但是矩形个数却比较小，此时不难想到离散化，离散化后，我们不再将坐标平面划分为面积为1的小方格，而是根据在n个矩形中出现过的坐标来划分，这样的话，最后划分出来出来的方格数目不会超过2n*2n，这样就不会超时了，虽然还是暴力统计。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 1010
int n;
int xl[N],xr[N];
int yl[N],yu[N];
int x[2*N],y[2*N],xcnt,ycnt;
bool flag[2*N][2*N];
int cmp(const void *a,const void *b)
{
    return *(int*)a-*(int*)b;
}
int bsx(int k)
{
    int min=0,max=xcnt,mid;
    while(min+1!=max)
    {
        mid=min+max>>1;
        if(x[mid]>k)    max=mid;
        else    min=mid;
    }
    return min;
}
int bsy(int k)
{
    int min=0,max=ycnt,mid;
    while(min+1!=max)
    {
        mid=min+max>>1;
        if(y[mid]>k)    max=mid;
        else    min=mid;
    }
    return min;
}
int main()
{
    int i,j,k;
    int a,b,c,d;
    while(~scanf("%d%d%d%d",&a,&b,&c,&d))
    {
        if(a==-1 && b==-1 && c==-1 && d==-1)    break;

        n=0;
        xcnt=ycnt=0;

        xl[n]=a;    yl[n]=b;
        xr[n]=c;    yu[n]=d;
        n++;
        x[xcnt++]=a;  x[xcnt++]=c;
        y[ycnt++]=b;  y[ycnt++]=d;

        while(scanf("%d%d%d%d",&a,&b,&c,&d))
        {
            if(a==-1 && b==-1 && c==-1 && d==-1)    break;

            xl[n]=a;    yl[n]=b;
            xr[n]=c;    yu[n]=d;
            n++;
            x[xcnt++]=a;  x[xcnt++]=c;
            y[ycnt++]=b;  y[ycnt++]=d;
        }
        qsort(x,xcnt,sizeof(int),cmp);
        qsort(y,ycnt,sizeof(int),cmp);

        k=xcnt;
        xcnt=0;
        x[xcnt++]=x[0];
        for(i=1;i<k;i++)    if(x[i]!=x[xcnt-1]) x[xcnt++]=x[i];

        k=ycnt;
        ycnt=0;
        y[ycnt++]=y[0];
        for(i=1;i<k;i++)    if(y[i]!=y[ycnt-1]) y[ycnt++]=y[i];

        for(i=0;i<xcnt;i++)  memset(flag[i],0,sizeof(bool)*(ycnt));

        for(k=0;k<n;k++)
        {
            a=bsx(xl[k]);    b=bsy(yl[k]);
            c=bsx(xr[k]);    d=bsy(yu[k]);
            for(i=a;i<c;i++)
            {
                for(j=b;j<d;j++)   flag[i][j]=true;
            }
        }
        int ans=0;
        for(i=0;i<xcnt-1;i++)
        {
            for(j=0;j<ycnt-1;j++)
            {
                if(flag[i][j])  ans+=(x[i+1]-x[i])*(y[j+1]-y[j]);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}