51nod1302 矩形面积交

有2N个矩形，这些矩形被标号为0 ~ 2N-1，对于第i个矩形其长宽分别为X[i]与Y[i]。现在要把这2N个矩形分为两组，每组N个，每个矩形恰好分到两组中的一组里。分成两组后，设两组分别为A组、B组，对于每一组矩形，你需要分别完成如下任务：
将该组中的N个矩形依次放在一个平面上，可以相互重叠，要求每个矩形的4条边都平行于平面坐标系的X轴或Y轴，矩形在摆放时可以旋转90度后再摆放。N个矩形摆放完后，使这N个矩形共同重叠的面积最大；设A组的最大面积为SA，B组的最大面积为SB。
请寻找一种恰当的分组方法，使SA+SB最大，并输出SA+SB的这个极值。
存在一组最优解，满足所有x>y的都被旋转了90度（即swap(x,y)）。
考虑x最小和y最小的矩形，如果有多个任选一个。如果x,y同时最小，那么只需在剩余2n-1个矩形中选n个使面积交最大，否则分类这两个某一维最小的矩形是否在同一组，如果同组的话类似的只需在剩余2n-2个矩形中选n个使面积交最大，不同组则把剩余2n-2个等分成两组，使第一组x最大，第二组y最大。这三个过程很类似，都可以枚举一维的最值，另一维的最值用堆优化贪心确定。

#include<bits/stdc++.h>

const int N=,inf=0x3f3f3f3f;

typedef long long i64;

int n,pp,mx=inf,my=inf,sd=;

int min(int a,int b){return a<b?a:b;}

void mins(int&a,int b){if(a>b)a=b;}

void maxs(i64&a,i64 b){if(a<b)a=b;}

struct pos{

    int x,y;

    void R(){

        scanf("%d%d",&x,&y);

        if(x>y)std::swap(x,y);

        mins(mx,x);mins(my,y);

    }

    bool operator<(const pos&w)const{return x<w.x;}

}ps[N],pmx,pmy;

struct cmpy1{bool operator()(const pos&a,const pos&b){return a.y>b.y;}};

struct cmpy2{bool operator()(const pos&a,const pos&b){return a.y<b.y;}};

i64 cal1(){

    i64 s=;

    if(!sd)sd=,std::sort(ps+,ps+pp+);

    std::priority_queue<pos,std::vector<pos>,cmpy1>q;

    for(int i=pp;i;--i){

        q.push(ps[i]);

        if(q.size()>n)q.pop();

        if(q.size()==n)maxs(s,q.top().y*i64(ps[i].x));

    }

    return s+i64(mx)*my;

}

int ys[N];

i64 cal2(){

    i64 s=;

    if(!sd)sd=,std::sort(ps+,ps+pp+);

    ys[]=inf;

    int y0=pmx.y;

    for(int i=;i<=pp;++i)ys[i]=ys[i-],mins(ys[i],ps[i].y);

    std::priority_queue<pos,std::vector<pos>,cmpy2>q;

    for(int i=pp;i;--i){

        q.push(ps[i]);

        if(q.size()>n-)mins(y0,q.top().y),q.pop();

        if(q.size()==n-)maxs(s,i64(min(ps[i].x,pmy.x))*my+i64(min(ys[i-],y0))*mx);

    }

    return s;

}

int main(){

    scanf("%d",&n);

    pp=n*;

    for(int i=;i<=pp;++i)ps[i].R();

    for(int i=;i<=pp;++i)if(ps[i].x==mx){pmx=ps[i];ps[i]=ps[pp--];break;}

    if(pmx.y==my)return printf("%lld",cal1()),;

    for(int i=;i<=pp;++i)if(ps[i].y==my){pmy=ps[i];ps[i]=ps[pp--];break;}

    return printf("%lld",std::max(cal1(),cal2())),;

}

51nod1302 矩形面积交的相关教程结束。