pku1177 Picture

#include<stdio.h>
#include<algorithm>
using namespace std;

const int Maxn=5000;
struct rectangle
{
    int x1,x2,y1,y2;
}rec[Maxn];
int horizontal[Maxn*2],vertical[Maxn*2],record[Maxn*2];    
int n;

int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}

int lookup(int s[],int key)                            
{
    int begin=0,end=2*n-1,middle;
    while(begin<=end)
    {
        middle=(begin+end)/2;
        if(s[middle]==key)
            return middle;
        else if(s[middle]>key)
            end=middle-1;
        else
            begin=middle+1;
    }
}

int count_x(int x1,int x2)
{
    int i;
    for(i=0;i<n;i++)
    {
        if(x1>=rec[i].x1&&x2<=rec[i].x2)    //该矩形横跨了该组超元线段

        {
            record[lookup(vertical,rec[i].y2)]++;    
            record[lookup(vertical,rec[i].y1)]--;    
        }
    }
    int sum=0,add=0;
    for(i=0;i<2*n;i++)
    {
        if(record[i]!=0)                
        {
            if(add==0)
                sum++;
            add+=record[i];
            if(add==0)
                sum++;
        }
    }
    return sum;
}

int count_y(int y1,int y2)
{
    int i;
    for(i=0;i<n;i++)
    {
        if(rec[i].y1<=y1&&rec[i].y2>=y2)
        {
            record[lookup(horizontal,rec[i].x2)]++;
            record[lookup(horizontal,rec[i].x1)]--;
        }
    }
    int sum=0,add=0;
    for(i=0;i<2*n;i++)
    {
        if(record[i]!=0)
        {
            if(add==0)
                sum++;
            add+=record[i];
            if(add==0)
                sum++;
        }
    }
    return sum;
}

int main()
{
    scanf("%d",&n);
    int i;
    for(i=0;i<n;i++)
    {
        scanf("%d%d%d%d",&rec[i].x1,&rec[i].y1,&rec[i].x2,&rec[i].y2);
        horizontal[i*2]=rec[i].x1;horizontal[i*2+1]=rec[i].x2;
        vertical[i*2]=rec[i].y1;vertical[i*2+1]=rec[i].y2;
    }

    qsort(horizontal,n*2,sizeof(int),cmp);
    qsort(vertical,n*2,sizeof(int),cmp);

    int length,amount,perimeter=0;
    for(i=0;i<n*2-1;i++)
    {
        length=horizontal[i+1]-horizontal[i];
        if(length!=0)                        
        {
            memset(record,0,sizeof(record));            ///记录矩形的上下两边横跨超元线段的情况

            amount=count_x(horizontal[i],horizontal[i+1]);
            perimeter+=length*amount;
        }
    }

    for(i=0;i<n*2-1;i++)
    {
        length=vertical[i+1]-vertical[i];
        if(length!=0)
        {
            memset(record,0,sizeof(record));            ///记录矩形的左右两边横跨超元线段的情况

            amount=count_y(vertical[i],vertical[i+1]);
            perimeter+=length*amount;
        }
    }

    printf("%d\n",perimeter);
    return 0;
}