Intersecting Rectangles Kattis – intersectingrectangles

题目链接

https://cn.vjudge.net/problem/Kattis-intersectingrectangles

题目大意

给出n个矩形,保证没有任何的x相同和y相同,问有没有相交的矩形,两个矩形的边有任意一个点重合即代表矩形相交。

解题思路

首先离散化,然后假想y轴是一个大数组。按照x从小到大的顺序遍历每个竖边。

若是矩形左边的边,则先查询一下y那个数组在当前边上下端点之间有没有1,有1代表当前有一条横边与这条竖边相交,也就是说有两个矩形相交了,最后再将y的那个数组在上下端点的y值处标记为1。

若是矩形右边的边,则先将当前的上下端点标记为0再查询。

为了不超时可以使用线段树或者树状数组实现。

代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct node
{
    int up,down,x,w;
} a[200010];
int b[400040],tot,bit[400040];
unordered_map<int,int>mp;
bool cmp(node x,node y)
{
    return x.x<y.x;
}
//树状数组部分
int low_bit(int x)
{
    return x&(-x);
}
void add(int id,int data)
{
    for(int i=id; i<=400040; i+=low_bit(i))
    {
        bit[i]+=data;
    }
}
int que(int k)
{
    int ans=0;
    for(int i=k; i>0; i-=low_bit(i))
    {
        ans+=bit[i];
    }
    return ans;
}
int main()
{
    int n;
    cin>>n;
    int x,y,xx,yy;
    tot=0;
    int cnt=0;
    for(int i=0; i<n; i++)
    {
        cin>>x>>y>>xx>>yy;
        a[cnt++]= {yy,y,x,1};
        a[cnt++]= {yy,y,xx,-1};
        b[tot++]=x;
        b[tot++]=y;
        b[tot++]=xx;
        b[tot++]=yy;
    }
    sort(b,b+tot);
    tot=unique(b,b+tot)-b;
    //离散化
    for(int i=0; i<tot; i++)
    {
        mp[b[i]]=i+1;
    }
    sort(a,a+cnt,cmp);
    long long ans=0;
    for(int i=0; i<cnt; i++)
    {
        int up=mp[a[i].up];
        int down=mp[a[i].down];
        if(a[i].w==1)//矩形左边的边
        {
            ans+=(que(up)-que(down));
            add(up,a[i].w);
            add(down,a[i].w);
        }
        else//矩形右边的边
        {
            add(up,a[i].w);
            add(down,a[i].w);
            ans+=(que(up)-que(down));
        }
    }
    if(ans!=0)
        cout<<"1"<<endl;
    else
        cout<<"0"<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注