HDU 5862 Counting Intersections

男娘i 2022-09-25 11:26 26阅读 0赞

题目链接：  
[http://acm.split.hdu.edu.cn/showproblem.php?pid=5862][http_acm.split.hdu.edu.cn_showproblem.php_pid_5862]

题目大意：给你很多平行X或Y轴的线段，求所有交点

解题思路：  
对于平行与Y轴的直线按端点的X坐标排序，从最左边的平行于Y轴的遍历到最右边的平行于Y轴的。  
对于一个平行于Y轴的线段L，一个平行于X轴的直线的左端点的若在在其右边那么肯定没交点，所以对所有平行于X轴的线段按左端点的X坐标排序，从头开始遍历直到遍历到左端点在L的右边停止，将符合条件的线段的右端点的X坐标压进优先队列里，并在对应的Y坐标加1，优先队列优越小的值优先级越高，压进之后判断队列顶的X是否大于线段L的X，若大于则相交，弹出所有小于线段X坐标的点，并在对应的Y坐标减1，答案数加上线段L两个Y坐标之间所有点的值的和。  
再选下一个线段L1，从上次停的点继续遍历直到结束。

每个点最多压进一次，弹出一次，求区间和用树状数组维护。

复杂度n^2\*logN\*logN

这道题大众解法是按每条线段的左端点的X,Y坐标排序，平行于X轴则对应Y坐标加1，平行于Y轴则直接y1-y2的区间和。

AC代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <list>
    #include <map>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <numeric>
    #include <functional>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    double EPS=1e-10;
    typedef long long LL;
    int n1=-1;
    struct P
    {
        int x1,y1;
        int x2,y2;
        void fu(int xx,int yy,int xxx,int yyy)
        {
            x1=xx;
            y1=yy;
            x2=xxx;
            y2=yyy;
            if(x1>x2)
            {
                swap(x1,x2);
                swap(y1,y2);
            }
        }
    };
    P p1[100005];//x
    
    P p2[100005];//y
    
    LL bit[500005],n;
    
    int x1[100005];
    int x2[100005];
    int y3[100005];
    int y4[100005];
    
    
    
    
    bool cmp(P p1,P p2)
    {
        if(p1.x1==p2.x1) return p1.x2<p2.x2;
        return p1.x1<p2.x1;
    }
    
    LL sum(LL i)
    {
        LL s=0;
        while(i>0)
        {
            s+=bit[i];
            i-=i&-i;
        }
        return s;
    }
    
    void add(LL i,LL x)
    {
        while(i<=n1)
        {
    
            bit[i]+=x;
            i+=i&-i;
    
        }
    }
    
    
    
    
    struct ex
    {
        int val;
        int poi;
    };
    
    struct cmp1
    {
        bool operator() (const ex a,const ex b) const
        {
            return a.val>b.val;
    
        }
    
    
    };
    
    priority_queue<ex,vector<ex>,cmp1> pq;
    
    int compress(int *x111,int *x222)
    {
        vector<int> xs;
        for(int i=0; i<n; i++)
        {
            for(int d=-1; d<=1; d++)
            {
                int tx1=x111[i]+d,tx2=x222[i]+d;
                xs.push_back(tx1);
                xs.push_back(tx2);
            }
        }
    
        sort(xs.begin(),xs.end());
        xs.erase(unique(xs.begin(),xs.end()),xs.end());
    
        for(int i=0; i<n; i++)
        {
            x111[i]=lower_bound(xs.begin(),xs.end(),x111[i])-xs.begin();
            x222[i]=lower_bound(xs.begin(),xs.end(),x222[i])-xs.begin();
        }
        return xs.size();
    }
    
    bool cmp3(P p1,P p2)
    {
        return p1.x1<p2.x1;
    }
    
    
    
    int main()
    {
        int T;
        RI(T);
        while(T--)
        {
            RI(n);
            n1=-1;
            memset(bit,0,sizeof(bit));
    
            int p1length=0;
            int p2length=0;
    
            for(int i=0; i<n; i++)
            {
                RII(x1[i],y3[i]);
                RII(x2[i],y4[i]);
            }
    
            compress(x1,x2);
            compress(y3,y4);
    
            for(int i=0; i<n; i++)
            {
                x1[i]+=1;
                y3[i]+=1;
                x2[i]+=1;
                y4[i]+=1;
                if(y3[i]==y4[i])
                {
                    n1=max(n1,y3[i]);
                    p1[p1length++].fu(x1[i],y3[i],x2[i],y4[i]);
                }
                else p2[p2length++].fu(x1[i],y3[i],x2[i],y4[i]);
            }
    
            sort(p1,p1+p1length,cmp);
            sort(p2,p2+p2length,cmp3);
            LL ans=0;
            int poi=0;
    
            for(int i=0; i<p2length; i++)
            {
    
                while(poi<p1length&&p1[poi].x1<=p2[i].x1)
                {
                    ex x;
                    x.poi=p1[poi].y1;
                    x.val=p1[poi].x2;
                    pq.push(x);
                    add(p1[poi].y1,1);
                    poi++;
    
                }
    
                while(!pq.empty()&&(pq.top().val<p2[i].x1))
                {
                    int x=pq.top().poi;
                    add(x,-1);
                    pq.pop();
                }
    
                LL y1=max(p2[i].y2,p2[i].y1);
                LL y2=min(p2[i].y2,p2[i].y1);
    
                if(y2-1==0) ans+=sum(y1);
                else  ans+=sum(y1)-sum(y2-1);
            }
    
            printf("%I64d\n",ans);
            while(!pq.empty())
            {
                pq.pop();
            }
    
        }
    
        return 0;
    }

[http_acm.split.hdu.edu.cn_showproblem.php_pid_5862]: http://acm.split.hdu.edu.cn/showproblem.php?pid=5862