TIOJ 1045 A.細菌培養

[離散暴力]

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#define LL long long int
using namespace std;
struct step
{
    LL ax,ay;
    LL bx,by;
    int x1,x2;
    int y1,y2;
}Steps[400];
int n;
void Print(LL *I,int cnt,const char *CC)
{
    printf("%s:",CC);
    for(int lx=0;lx<cnt;lx++)
        printf("%I64d ",I[lx]);
    printf("\n");
}
int Cut(LL *I,int cnt)
{
    sort(I,I+cnt);
    int re=1;
    for(int lx=1;lx<cnt;lx++)
        if(I[lx]!=I[lx-1])
            I[re++]=I[lx];
    return re;
}
LL field[440][440];
LL xax[1000],yax[1000];
int xpc,ypc;
void PrintField()
{
    for(int lx=0;lx<xpc-1;lx++)
    {
        for(int ly=0;ly<ypc-1;ly++)
            printf("%I64d ",field[lx][ly]);
        printf("\n");
    }
    printf("===============================\n");
}
int main()
{
    while(scanf("%d",&n)&&n)
    {
        int xcnt=0,ycnt=0;
        xax[xcnt++]=0;xax[xcnt++]=10000;
        yax[ycnt++]=0;yax[ycnt++]=10000;
        for(int lx=0;lx<n;lx++)
        {
            scanf("%I64d %I64d %I64d %I64d",&Steps[lx].ax,&Steps[lx].ay,&Steps[lx].bx,&Steps[lx].by);
            xax[xcnt++]=Steps[lx].ax;xax[xcnt++]=Steps[lx].bx;
            yax[ycnt++]=Steps[lx].ay;yax[ycnt++]=Steps[lx].by;
        }
        xpc=Cut(xax,xcnt);
        ypc=Cut(yax,ycnt);
        //Print(xax,xpc,"XAX:");
        //Print(yax,ypc,"YAX:");
        for(int lx=0;lx<n;lx++)
        {
            for(int ly=0;ly<xpc;ly++)
            {
                if(xax[ly]==Steps[lx].ax)
                    Steps[lx].x1=ly;
                else if(xax[ly]==Steps[lx].bx)
                    Steps[lx].x2=ly-1;
            }
            for(int ly=0;ly<ypc;ly++)
            {
                if(yax[ly]==Steps[lx].ay)
                    Steps[lx].y1=ly;
                else if(yax[ly]==Steps[lx].by)
                    Steps[lx].y2=ly-1;
            }
        }
        for(int lx=0;lx<xpc-1;lx++)
            for(int ly=0;ly<ypc-1;ly++)
                field[lx][ly]=(xax[lx+1]-xax[lx])*(yax[ly+1]-yax[ly]);
        //PrintField();
        //for(int lx=0;lx<n;lx++)
        //  printf("[%d %d %d %d]\n",Steps[lx].x1,Steps[lx].x2,Steps[lx].y1,Steps[lx].y2);
        for(int lp=0;lp<n;lp++)
        {
            for(int lx=Steps[lp].x1;lx<=Steps[lp].x2;lx++)
                for(int ly=Steps[lp].y1;ly<=Steps[lp].y2;ly++)
                    field[lx][ly]*=2;
            //PrintField();
        }

        LL ANS=0;
        for(int lx=0;lx<xpc-1;lx++)
            for(int ly=0;ly<ypc-1;ly++)
                ANS+=field[lx][ly];
        printf("%I64d\n",ANS);
    }

    return 0;
}