City Planning

Problem Description

After many years, the buildings in HDU has become very old. It need to rebuild the buildings now. So Mr dragon (the president of HDU‘s logistics department ) ask Mr Wan (a very famous engineer) for help.
Mr Wan only draw one building on a construction design drawings(all the buildings are rectangle and each edge of buildings‘ is paraller or perpendicular to others buildings‘ edge ). And total draw n drawings (all the drawings have same width and length . And bottomleft point is (0, 0)). Due to possible overlap of conditions, so when they build a new building, they should to remove all the overlapping part of it. And for each building, HDU have a jury evaluate the value per unit area. Now Mr dragon want to know how to arrange the order of build these buildings can make the highest value.

 

Input

The first line of input is a number T which indicate the number of cases . (1 < T < 3000);
Each test case will begin with a single line containing a single integer n (where 1 <= n <= 20). 
Next n line will contain five integers x1, y1, x2, y2 ,value . x1,y1 is bottomleft point and x2,y2 is topright point , value is the value of the buildings‘ unit area.((0 <= x1, y1, x2, y2 <= 10000) (x1 < x2, && y1 < y2) (1 <= value <= 22)

 

Output

For each case. You just ouput the highest value in one line.

 

Sample Input

1
3
1 1 10 10 4
4 4 15 5 5
7 8 20 30 6

 

Sample Output

Case 1: 2047




题意 :
 给你n个矩形  每一个矩形都有自己的val  ,对于重合的面积，val大的能将小的覆盖，求总val的最大值 。
思路：
听说是扫描线，然后去学了扫描线，发现事实上暴力也能够。
代码：
（暴力）
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
typedef long long ll;  
const int N = 50;  
int y[N], x[N], n, m;  
ll val[N][N];  
struct Rect  
{  
    int x1, y1, x2, y2, v;  
    bool operator< (const Rect &r) const{  
        return v < r.v;  
    }  
} r[N];   
int fid(int a[], int k){  
    return lower_bound(a, a + m, k) - a;  
}  
  
int main()  
{  
    int T, x1, y1, x2, y2, cas = 0;  
    scanf("%d", &T);  
    while(T--)  
    {  
        scanf("%d", &n);  
        for(int i = m = 0; i < n; ++i, m += 2)  
        {  
            scanf("%d%d%d%d%d", &r[i].x1, &r[i].y1, &r[i].x2, &r[i].y2, &r[i].v);  
            x[m] = r[i].x1, x[m + 1] = r[i].x2;  
            y[m] = r[i].y1, y[m + 1] = r[i].y2;  
        }  
        sort(r, r + n); //将value小的大楼放前面  
        sort(x, x + m); //离散化x  
        sort(y, y + m); //离散化y  
  
        memset(val, 0, sizeof(val));  
        for(int i = 0; i < n; ++i)  
        {  
            x1 = fid(x, r[i].x1), x2 = fid(x, r[i].x2);  //获得x离散化后的坐标  
            y1 = fid(y, r[i].y1), y2 = fid(y, r[i].y2);  //获得y离散化后的坐标  
            for(int j = x1; j < x2; ++j)  
                for(int k = y1; k < y2; ++k)  val[j][k] = r[i].v;  
        }  
  
        ll ans = 0;  
        for(int i = 0; i < m - 1; ++i)  
            for(int j = 0; j < m - 1; ++j)  
                ans += val[i][j] * (x[i + 1] - x[i]) * (y[j + 1] - y[j]);  
        printf("Case %d: %I64d\n", ++cas, ans);  
    }  
    return 0;  
}  
扫描线（求体积并）：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=50;
#define lson L,mid,ls
#define rson mid+1,R,rs
typedef long long ll;
struct node
{
    int x1,x2,h,val,tag;
    node(int a=0,int b=0,int c=0,int d=0,int e=0):x1(a),x2(b),h(c),val(d),tag(e){}
    bool operator<(const node &op) const
    {
        return h<op.h;
    }
}seg[N],tp[N];
int len[N<<2],cov[N<<2],val[N],H[N];
void build(int L,int R,int rt)
{
    len[rt]=cov[rt]=0;
    if(L==R) return;
    int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
    build(lson);
    build(rson);
}
void update(int L,int R,int rt,int l,int r,int d)
{
    if(l<=L&&R<=r)
    {
        cov[rt]+=d;
        len[rt]=cov[rt]?H[R]-H[L-1]:(L==R?0:len[rt<<1]+len[rt<<1|1]);
        return;
    }
    int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
    if(l<=mid) update(lson,l,r,d);
    if(r>mid)  update(rson,l,r,d);
    len[rt]=cov[rt]?H[R]-H[L-1]:len[ls]+len[rs];
}
int main()
{
    int t,n,x1,x2,y1,y2,v,f=1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int ct=0,m=0,nv=1;
        val[0]=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&v);
            seg[ct++]=node(x1,x2,y1,v,1),seg[ct++]=node(x1,x2,y2,v,-1);
            H[m++]=x1,H[m++]=x2;
            val[nv++]=v;
        }
        sort(seg,seg+ct);
        sort(H,H+m);
        m=unique(H,H+m)-H;
        sort(val,val+nv);
        ll ans=0;
        for(int i=0;i<nv;i++)
        {
            int nt=0;
            for(int j=0;j<ct;j++)
                if(seg[j].val>val[i]) tp[nt++]=seg[j];
            build(1,m-1,1);
            ll tt=0;
            for(int j=0;j<nt-1;j++)
            {
                int l=lower_bound(H,H+m,tp[j].x1)-H+1;
                int r=lower_bound(H,H+m,tp[j].x2)-H;
                update(1,m-1,1,l,r,tp[j].tag);
                tt+=(ll)len[1]*(tp[j+1].h-tp[j].h);求在某一高度面积
            }
            ans+=tt*(val[i+1]-val[i]);求体积
        }
        printf("Case %d: %I64d\n",f++,ans);
    }
    return 0;
}
另外再学习扫描线时的线段并：
<pre name="code" class="cpp">#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100010;
#define lson L,mid,ls
#define rson mid+1,R,rs
struct node
{
    int x1,x2,cmd;
} seg[maxn];
int X[maxn<<1];
int len[maxn<<2],cov[maxn<<2];//len[rt]为结点被覆盖的长度。
cov[rt]表示是否被整个覆盖
void build(int L,int R,int rt)//线段树的L,R表示X[L]~X[R+1]的线段
{
    len[rt]=cov[rt]=0;
    if(L==R)
        return;
    int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
    build(lson);
    build(rson);
}
void PushDown(int L,int R,int rt)
{
    int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
    if(cov[rt]==1)
    {
        cov[ls]=cov[rs]=1;
        len[ls]=X[mid]-X[L-1];//因为X下标从0開始.所以L,R都要减1。下同
        len[rs]=X[R]-X[mid];
    }
    else
    {
        cov[ls]=cov[rs]=-1;
        len[ls]=len[rs]=0;
    }
    cov[rt]=0;
}
void update(int L,int R,int rt,int l,int r,int d)
{
    if(l<=L&&R<=r)
    {
        if(d==1)//表示覆盖
            cov[rt]=1,len[rt]=X[R]-X[L-1];
        else
            cov[rt]=-1,len[rt]=0;
        return;
    }
    int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
    if(cov[rt])
        PushDown(L,R,rt);
    if(l<=mid)
        update(lson,l,r,d);
    if(r>mid)
        update(rson,l,r,d);
    len[rt]=len[ls]+len[rs];
    printf("%d->%d len %d\n",X[L-1],X[R],len[rt]);
}
int main()
{
    int t,n,m,i;

    scanf("%d",&t);//t组測试数据
    while(t--)
    {
        scanf("%d",&n);//2个操作。1插入线段x1,x2。-1删除x1,x2之间的线段。
        m=0;           //每次操作后输出x轴被覆盖的长度
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%d",&seg[i].x1,&seg[i].x2,&seg[i].cmd);
            X[m++]=seg[i].x1,X[m++]=seg[i].x2;
        }
        sort(X,X+m);
        m=unique(X,X+m)-X;//m个点就有m-1个线段第i个点代表线段X[i]~X[i+1]
        build(1,m-1,1);
        for(i=1;i<=n;i++)
        {
            int l=lower_bound(X,X+m,seg[i].x1)-X+1;
            int r=lower_bound(X,X+m,seg[i].x2)-X+1;
            //printf("update %d->%d\n",X[l])
            update(1,m-1,1,l,r-1,seg[i].cmd);
            printf("%d\n",len[1]);
        }
    }
    return 0;
}
3
3
1 2 1
2 3 1
3 4 1
4
1 2 1
2 3 1
3 4 1
2 3 -1
还有面积并：点击打开链接