Olddriver 的书多的吓人,什么算法导论,组合数学英

文版(orz)。。。。。。他把 n 本书都放在身后的桌子上,

每本书有一定的面积,并且书可以覆盖,求 n 本书覆盖桌面

的面积

输入格式:

输入第一行为一个数 N,表示书的数量。下面 N 行,每行

四个整数,分别表示每个书的左下角和右上角的坐标。

输出格式:

输出只有一行,一个整数,表示图形的面积。

样例输入:

3

1 1 4 3

2 -1 3 2

4 0 5 2

样例输出:

10

数据范围:

对于 30%的数据:n<=100,坐标数值绝对值<=300

对于 100%的数据:n<=100,坐标数值绝对值<=10^8

【题解】

对于30%数据 打标记。

对于100%数据，注意到点最多有200个，对x，y坐标离散化，再打标记。

考试时没想到离散化（但数据范围是个很明显的暗示）。要试着接纳这道题的思维。

另外，离散化后要去重（然而我并不知道为什么）。

//这道题写什么扫描线

//离散化以后　直接暴力写不就好了么　O(n^3) 数据真是良心

#include<cstdio>

#include<algorithm>

using namespace std;

const int MAX=510;

struct books

{

    int x1,y1,x2,y2;

}c[MAX];

bool b[MAX][MAX];//某一区域上是否有书覆盖　注意是区域而不是点

int x[MAX],y[MAX];

int rx[MAX],ry[MAX],tx,ty;

int n,cnt;

long long ans;

int gi()

{

    int x=0,w=1;char ch=getchar();

    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

    if (ch=='-') w=-1,ch=getchar();

    while (ch>='0'&&ch<='9')

    {

        x=x*10+ch-'0';

        ch=getchar();

    }

    return x*w;

}

//手写lower_bound

int pos_x(int x)

{

    int l=1,r=tx;

    while (l<r)

    {

        int mid=(l+r+1)>>1;

        if (rx[mid]<=x) l=mid;

        else r=mid-1;

    }

    return l;

}

//手写*2

int pos_y(int x)

{

    int l=1,r=ty;

    while (l<r)

    {

        int mid=(l+r+1)>>1;

        if (ry[mid]<=x) l=mid;

        else r=mid-1;

    }

    return l;

}

int main()

{

    freopen("olddriver.in","r",stdin);

    freopen("olddriver.out","w",stdout);

    n=gi();

    for (int i=1;i<=n;i++)

    {

        c[i].x1=gi();c[i].y1=gi();c[i].x2=gi();c[i].y2=gi();

        x[++cnt]=c[i].x1;y[cnt]=c[i].y1;

        x[++cnt]=c[i].x2;y[cnt]=c[i].y2;

    }

    sort(x+1,x+cnt+1);

    sort(y+1,y+cnt+1);

    for (int i=1;i<=cnt;i++)//去重

    {

        if (i==1||x[i]!=x[i-1]) rx[++tx]=x[i];

        if (i==1||y[i]!=y[i-1]) ry[++ty]=y[i];

    }

    for (int i=1;i<=n;i++)//暴力枚举每一本书

    {

        int X1=pos_x(c[i].x1),X2=pos_x(c[i].x2);

        int Y1=pos_y(c[i].y1),Y2=pos_y(c[i].y2);

        for (int u=X1;u<X2;u++)

            for (int v=Y1;v<Y2;v++)

                b[u][v]=1;

    }

    for (int u=1;u<tx;u++)

        for (int v=1;v<ty;v++)

            if (b[u][v]) ans+=1ll*(rx[u+1]-rx[u])*(ry[v+1]-ry[v]);

    printf("%lld",ans);

    return 0;

}