题解

116 条题解

  • 5
    @ 2018-10-09 21:02:14

    我的博客

    题解

    这里有篇很好的文章,对于深入理解有帮助

    对于这道题目,第一想法就是用bool数组标记,最后统和,但是奈何数据范围不允许。

    可以用扫描线+线段树维护,但是总觉得有点大动干戈。

    而“离散化”这一奇妙的思想能帮我们优雅地解决这道题(然而样例不能很好体现)

    我们首先来看看样例



    其中一样的颜色的点为一对输入(一个矩形),我们取出它们的横纵坐标,去重,排序,然后再去枚举,就得到了那些黑色的点。(有些和有颜色的点重复了)

    其实到了这一步我们已经离散化了(还没明白?别急,先往下看)

    于是我们枚举每一个黑色的点,让它和它右上方的黑点构成一个矩形,如果这个矩形在任意输入矩形内部,则对答案有贡献

    这样子我们就做到了不重不漏(黑点枚举出来的矩形不重复,并且黑点构成的全部矩形肯定把输入矩形囊括在内)

    到这里貌似就结束了,但是这种方法看上去还是在数格子?

    让我们把输入改成


    3
    1 1 4 4
    2 -1 3 3
    4 0 5 3

    再看看图像


    我们的枚举量并没有随着坐标范围变大而变大,并且还是做到了不重不漏,其原因就是我们在枚举黑点的时候,本来是2的距离,转化成了该点与上个点相差2,而空间上这两个点还是相邻的,这就是离散化。

    上面已经解释得很清楚了,代码就不写注释了。

    代码

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int MAXN=203;
    long long x[MAXN],y[MAXN],x1[MAXN],x2[MAXN],y1[MAXN],y2[MAXN];
    long long S,ans;
    int n;
    
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%lld%lld%lld%lld",&x1[i],&y1[i],&x2[i],&y2[i]);
            x[2*i-1]=x1[i];
            y[2*i-1]=y1[i];
            x[2*i]=x2[i];
            y[2*i]=y2[i];
        }
        sort(x+1,x+2*n+1);
        sort(y+1,y+2*n+1);//这里忘了去重,如果有重复的,(x[i+1]-x[i])*(y[j+1]-y[j])必定有一项为0,对答案没贡献
        for(int i=1;i<=2*n-1;i++){
            for(int j=1;j<=2*n-1;j++){
                S=(x[i+1]-x[i])*(y[j+1]-y[j]);
                for(int k=1;k<=n;k++){
                    if(x[i]>=x1[k]&&y[j]>=y1[k]&&x[i+1]<=x2[k]&&y[j+1]<=y2[k]){
                        ans+=S;
                        break;
                    }
                }
            }
        }
        cout<<ans;
        return 0;
    } 
    
    
  • 1
    @ 2019-04-28 13:36:38

    题目都说了是矩形。。。输入还能不合法。。。出题人心里没点高数吗

  • 1
    @ 2017-02-07 09:43:08
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #define N 1001
    using namespace std;
    
    long long n,num=1,Num=1,lfx[N],lfy[N],rtx[N],rty[N],x[N],y[N],a[N],b[N];
    long long flag[N][N],rec[N][N],ans;
    
    int main()
    {
        scanf("%d",&n);
        
        for(int i=1;i<=n;i++){
            cin>>lfx[i]>>lfy[i]>>rtx[i]>>rty[i];
            a[2*i-1]=lfx[i];a[2*i]=rtx[i];
            b[2*i-1]=lfy[i];b[2*i]=rty[i];
        }
        sort(a+1,a+1+2*n);
        sort(b+1,b+1+2*n);
        x[1]=a[1],y[1]=b[1];
        for(int i=2;i<=2*n;i++){
            if(a[i]!=a[i-1])
                x[++num]=a[i];
        }
        for(int i=2;i<=2*n;i++){
            if(b[i]!=b[i-1])
                y[++Num]=b[i];
        }
        for(int i=1;i<=num-1;i++)
            for(int j=1;j<=Num-1;j++)
                for(int k=1;k<=n;k++)
                    if(x[i]>=lfx[k]&&x[i+1]<=rtx[k]&&y[j]>=lfy[k]&&y[j+1]<=rty[k])
                        flag[i][j]=1;
        for(int i=1;i<=num-1;i++)
            for(int j=1;j<=Num-1;j++)
                rec[i][j]=abs((x[i+1]-x[i])*(y[j+1]-y[j]));
        for(int i=1;i<=num-1;i++)
            for(int j=1;j<=Num-1;j++)
                if(flag[i][j])
                    ans+=rec[i][j];
        cout<<ans;
        return 0;
    }
    
  • 1
    @ 2012-08-02 16:25:29

    排序离散化,卡在#4,晕死~~矩阵还可以是不合法的~~cheat了#4才AC~

  • 0
    @ 2018-08-18 16:42:11

    很水的一道题,我就不多说啦,就直接离散,关键操作我就注释代码里面啦。。。。。。
    ```cpp
    #include<iostream>
    #include<cstdio>
    #define MAX 250
    using namespace std;
    long long n,x1[MAX],y1[MAX],x2[MAX],y2[MAX],ans;
    long long zb[2][MAX*2];//嫌麻烦,直接把x和y存在一起了,zb[0]表示x,zb[1]表示y

    void quicksort(long long left,long long right,long long k)
    {
    long long i,j,mid,t;
    i=left; j=right; mid=zb[k][(i+j)/2];
    while (i<j)
    {
    while (zb[k][i]<mid) i++;
    while (zb[k][j]>mid) j--;
    if (i<=j)
    {
    t=zb[k][i]; zb[k][i]=zb[k][j]; zb[k][j]=t;
    i++; j--;
    }
    }
    if (left<j) quicksort(left,j,k);
    if (i<right) quicksort(i,right,k);
    }

    int main()
    {
    scanf("%I64d",&n);
    for (int i=1; i<=n; i++)
    {
    scanf("%I64d %I64d %I64d %I64d",&x1[i],&y1[i],&x2[i],&y2[i]);
    ans++;
    zb[0][ans]=x1[i]; zb[1][ans]=y1[i];
    ans++;
    zb[0][ans]=x2[i]; zb[1][ans]=y2[i];
    }

    quicksort(1,2*n,0);
    quicksort(1,2*n,1);

    ans=0;
    for (int i=1; i<2*n; i++)
    for (int j=1; j<2*n; j++)
    {
    long long mj=(zb[0][i+1]-zb[0][i])*(zb[1][j+1]-zb[1][j]);
    for (int k=1; k<=n; k++)//判断有没有原来的矩形覆盖当前枚举的i,j;
    if (zb[0][i]>=x1[k]&&zb[0][i+1]<=x2[k]&&zb[1][j]>=y1[k]&&zb[1][j+1]<=y2[k])
    {
    ans+=mj; break;//找到就直接退出循环k
    }
    }

    printf("%I64d",ans);
    return 0;
    }
    ```

  • 0
    @ 2017-10-25 17:21:04

    题解与楼下某位的思路类似
    不用离散化,暴力过
    代码如下(由于非常好懂,就不多解释了)

    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <queue>
    #include <vector>
    #include <map>
    #define N 1000000+100
    using namespace std;
    long long n,nx,ny,ans,sum1,sum2,leftx[501],lefty[501],rightx[501],righty[501],flag[501][501],rec[501][501],x[501],y[501];
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>leftx[i]>>lefty[i]>>rightx[i]>>righty[i];
            x[++sum1]=leftx[i];
            y[++sum2]=lefty[i];
            x[++sum1]=rightx[i];
            y[++sum2]=righty[i];
        }
        sort(x+1,x+1+sum1);
        sort(y+1,y+1+sum2);
        for(int i=1;i<=sum1;i++)
            if(x[i]!=x[i-1])
                x[++nx]=x[i];
        for(int i=1;i<=sum2;i++)
            if(y[i]!=y[i-1])
                y[++ny]=y[i];
        for(int i=1;i<=nx-1;i++)
            for(int j=1;j<=ny-1;j++)
                rec[i][j]=abs((x[i+1]-x[i])*(y[j+1]-y[j]));
        for(int i=1;i<=nx-1;i++)
            for(int j=1;j<=ny-1;j++)
                for(int k=1;k<=n;k++)
                    if(x[i]>=leftx[k]&&x[i+1]<=rightx[k]&&y[j]>=lefty[k]&&y[j+1]<=righty[k])
                        flag[i][j]=1;
        for(int i=1;i<=nx-1;i++)
            for(int j=1;j<=ny-1;j++)
                if(flag[i][j]==1)
                    ans+=rec[i][j];
        cout<<ans;
        return 0;
    }
    
    
  • 0
    @ 2010-04-07 19:25:39

    编译通过...├ 测试数据 01:答案正确...ms├ 测试数据 02:答案正确...ms├ 测试数据 03:答案正确...ms├ 测试数据 04:答案正确...ms├ 测试数据 05:答案正确...ms├ 测试数据 06:答案正确...ms├ 测试数据 07:答案正确...ms├ 测试数据 08:答案正确...ms├ 测试数据 09:答案正确...ms├ 测试数据 10:答案正确...msAccepted 有效得分:100 有效耗时:0ms

    离散化+线段树。。。

    按x离散化并建立线段树,然后把平行于x轴的扫描线插入到线段树中,算出实时覆盖长度,然后就不用我说了吧、、、、、

    PS. 强烈BS楼下的 题解王: 赫敏·格兰杰

  • 0
    @ 2010-03-13 15:17:53

    Accepted 有效得分:100 有效耗时:0ms

    50分的同志们注意一下,答案是int64的 T^T

    如果还是50分的同志们在注意一下,int64是不能要inc的 T^T

    今天我彻底悲剧了 T^T

  • 0
    @ 2009-11-09 10:41:02

    在 275616951 大牛的指导下

    我成功地

    AC!!!!!!!!!!

    orz 275616951 大牛

  • 0
    @ 2009-11-08 12:18:48

    program p1056;

    type node=record

    x1,x2,y1,y2:longint;

    end;

    var w:array[1..200]of node;

    i,n:longint;

    ans:int64;

    procedure init;

    var i,j:longint;

    begin

    readln(n);

    for i:=1 to n do

    readln(w[i].x1,w[i].y1,w[i].x2,w[i].y2);

    end;

    procedure cut(x1,x2,y1,y2:int64;t:longint);

    begin

    if (x1>=x2)or(y1>=y2) then exit;

    while (t>=1)and((x1>=w[t].x2)or(x2=w[t].y2)or(y2

  • 0
    @ 2009-11-06 20:45:55

    靠...int64....

    为此我WA了,n次....

  • 0
    @ 2009-11-06 20:08:56

    通过率这么低的原因是:

    1:int64;(没有40分)

    2:输入的矩形不一定合法(没pd90)

  • 0
    @ 2009-11-03 21:00:11

    INT64

  • 0
    @ 2009-11-03 10:17:28

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    离散,更快更好写

  • 0
    @ 2009-11-03 00:02:25

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    矩形分割,既快又好写~

  • 0
    @ 2009-11-02 23:55:54

    不是说“坐标范围为–10^8到10^8之间的整数。”吗?为什么用longint还是不行?分明是题目有问题嘛。

  • 0
    @ 2009-11-02 21:07:09

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    万恶的数据。。。万恶的int64,同样的程序,只是数据类型的差异,竟然害我WA了三次;

    虽然如此。。。还是在此Orz 一下Matrix67神牛,真是神奇的离散化。。

  • 0
    @ 2009-10-27 19:10:34

    神奇的离散化~膜拜Matrix67神牛~~

    居然因为数据没开到int64交了N次。。。。

  • 0
    @ 2009-10-21 21:05:32

    这题讲两个做法:

    一种是离散化,也就是将原平面,对于每一个Y坐标,做直线Y=Yi,对每个X坐标,做直线X=Xi,此时分成很多个矩形,则这些矩形要么被某个矩形完全覆盖,要么不被任何矩形覆盖(相交)。

    则可以模拟一条扫描线,维护每两条相邻的竖线之间有多少个小矩形被覆盖即可。每一个小矩形可以用一个Y坐标来离散。

    第二种做法是朴素,也就是扫描线过去,把相应位置染色,实现的时候,在添加区间时,若走到了个新区间则开一个新空间给这个位置并继续下传,询问的时候,如果儿子为空则表示对应区间没有被染色。这样就可以用nlogn的空间解决这道题了。

    hint:线段树区间负数正数都有的时候,若当前区间为(l,l+1),那一定要记得讨论分区间,不然会死循环

  • 0
    @ 2009-10-12 22:36:21

    很神奇的离散❀撒

信息

ID
1056
难度
7
分类
计算几何 点击显示
标签
(无)
递交数
3098
已通过
688
通过率
22%
上传者