Counting Intersections

  
  

   
   2
4
1 0 1 3
2 0 2 3
0 1 3 1
0 2 3 2
4
0 0 2 0
3 0 3 2
3 3 1 3
0 3 0 2
  
  

  
  

   
   4
0
  
  

【思路】

将给定的线段处理为点，若线段与x轴平行，则保留左右端点，点的up值与down值都等于纵坐标，若线段与y轴平行，则处理作一个点，down值为下端点纵坐标，up值为上端点纵坐标，于是得到了三类点，kind为0代表左端点，kind为1代表竖线段，kind为2代表右端点。然后把点按照从左到右的顺序进行排序，再用扫描线从左到右扫一遍来统计交点个数就好了，统计时要用到树状数组单点更新、区间查询的操作。扫描线扫到的点，首先看是哪种类型的，若是左端点，则给这个点的纵坐标加1，若是竖线段，则计算出数组的[down，up]区间和，这些就是与该竖线段的交点数，若是右端点，则给这个点的纵坐标减1。这一过程应严格按照这个顺序，因为可能出现线段呈T形相交的情况。由于纵坐标的范围很大，所以要先离散化再维护树状数组。

【代码】

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;

const int MAXN=100005;

struct point{
    int kind,pos,up,down;

    bool operator<(const point &another)const
    {
        if(pos==another.pos)
            return kind<another.kind;
        return pos<another.pos;
    }
};

int t,n,cnt,tot;
int height[MAXN*2];
long long a[MAXN*2];
point p[MAXN*2];
map<int,int> id;

void swap(int *a,int *b)
{
    *a=*a^*b;
    *b=*a^*b;
    *a=*a^*b;
}

int lowbit(int x)
{
    return (x&-x);
}

void modify(int x,int num)
{
    while(x<=tot){
        a[x]+=num;
        x+=lowbit(x);
    }
}

long long sum(int x)
{
    long long ans=0;
    while(x>0){
        ans+=a[x];
        x-=lowbit(x);
    }
    return ans;
}

int main()
{
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        cnt=0;tot=0;
        id.clear();
        for(int i=1;i<=n;i++){
            int x1,y1,x2,y2;
            scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
            if(!id.count(y1)){
                id[y1]=0;
                height[++tot]=y1;
            }
            if(!id.count(y2)){
                id[y2]=0;
                height[++tot]=y2;
            }
            if(x1==x2){
                if(y1>y2)swap(&y1,&y2);
                p[++cnt].kind=1;p[cnt].pos=x1;
                p[cnt].down=y1;p[cnt].up=y2;
            }
            else
            if(y1==y2){
                if(x1>x2)swap(&x1,&x2);
                p[++cnt].kind=0;p[cnt].pos=x1;
                p[cnt].up=p[cnt].down=y1;
                p[++cnt].kind=2;p[cnt].pos=x2;
                p[cnt].up=p[cnt].down=y2;
            }
        }
        sort(height+1,height+1+tot);
        for(int i=1;i<=tot;i++)
            id[height[i]]=i;
        sort(p+1,p+1+cnt);
        memset(a,0,sizeof(a));
        long long ans=0;
        for(int i=1;i<=cnt;i++){
            if(p[i].kind==0)
                modify(id[p[i].up],1);
            if(p[i].kind==1)
                ans+=(sum(id[p[i].up])-sum(id[p[i].down]-1));
            if(p[i].kind==2)
                modify(id[p[i].up],-1);
        }
        printf("%lldn",ans);
    }
    return 0;
}

最后

以上就是陶醉手机为你收集整理的HDU 5862 Counting Intersections（树状数组+离散化+扫描线） Counting Intersections的全部内容，希望文章能够帮你解决HDU 5862 Counting Intersections（树状数组+离散化+扫描线） Counting Intersections所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。