Counting Intersections HDU - 5862（离散化+树状数组）

130 阅读 0 评论 86 点赞

我是靠谱客的博主开朗棒棒糖，这篇文章主要介绍Counting Intersections HDU - 5862（离散化+树状数组），现在分享给大家，希望可以做个参考。

Given some segments which are paralleled to the coordinate axis. You need to count the number of their intersection.

The input data guarantee that no two segments share the same endpoint, no covered segments, and no segments with length 0.
Input
The first line contains an integer T, indicates the number of test case.

The first line of each test case contains a number n(1<=n<=100000), the number of segments. Next n lines, each with for integers, x1, y1, x2, y2, means the two endpoints of a segment. The absolute value of the coordinate is no larger than 1e9.
Output
For each test case, output one line, the number of intersection.
Sample Input
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
Sample Output
4
0

这个问题在于如何高效的去枚举了，我们去枚举所有的竖线，并把所有的横线拆成两个点，如果是左端点，标记为0，如果是右端点，标记为1。说不清楚，看代码

复制代码

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
#define N 100005
using namespace std;
int n;
int c[N*2];
int total;
int lowBit(int x)
{
    return x&-x;
}
int sum(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=c[x];
        x-=lowBit(x);
    }
    return ans;
}
void change(int x,int p)
{
    while(x<=total)
    {
        c[x]+=p;
        x+=lowBit(x);
    }
}//树状数组
struct node
{
    int x,y1,y2;
}seg[N];//竖线结构体
int cmp1(node s1,node s2)
{
    return s1.x<s2.x;
}
int k1;
struct P
{
    int x,y;
    int type;
}point[N*2];//点结构体
int cmp2(P l1,P l2)
{
    if(l1.x==l2.x)
        return l1.type<l2.type;
    return l1.x<l2.x;
}
int k2;
int num[N*2];
int k3;
int getInd(int y)//由实际值得到离散值
{
    return lower_bound(num,num+total,y)-num+1;
}
int main()
{
    int t;
    int x1,x2,y1,y2;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        memset(c,0,sizeof(c));
        k1=k2=k3=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            if(x1==x2)//竖线
            {
                num[k3++]=y1;
                num[k3++]=y2;//只离散y值
                if(y1>y2)
                {
                    int temp=y1;
                    y1=y2;
                    y2=temp;
                }
                seg[k1].x=x1;
                seg[k1].y1=y1;
                seg[k1].y2=y2;
                k1++;
            }
            else
            {
                num[k3++]=y1;
                if(x1>x2)
                {
                    int temp=x1;
                    x1=x2;
                    x2=temp;
                }
                point[k2].x=x1;
                point[k2].y=y1;
                point[k2].type=0;//把横线给拆掉
                k2++;
                point[k2].x=x2;
                point[k2].y=y1;
                point[k2].type=1;
                k2++;
            }
        }
        sort(seg,seg+k1,cmp1);
        sort(point,point+k2,cmp2);
        sort(num,num+k3);//各自的排序
        total=unique(num,num+k3)-num;
        long long ans=0;
        for(int i=0,j=0;i<k1;i++)//枚举竖线
        {
            while(j<k2&&(point[j].x<seg[i].x||(point[j].x==seg[i].x&&point[j].type==0)))//把所有横坐标小于竖线的横坐标的点的y值更新到树状数组
            {
                if(point[j].type==0)
                    change(getInd(point[j].y),1);
                else
                    change(getInd(point[j].y),-1);
                j++;
            }
            ans+=sum(getInd(seg[i].y2))-sum(getInd(seg[i].y1)-1);//统计答案
        }
        printf("%lldn",ans);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
#define N 100005
using namespace std;
int n;
int c[N*2];
int total;
int lowBit(int x)
{
    return x&-x;
}
int sum(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=c[x];
        x-=lowBit(x);
    }
    return ans;
}
void change(int x,int p)
{
    while(x<=total)
    {
        c[x]+=p;
        x+=lowBit(x);
    }
}//树状数组
struct node
{
    int x,y1,y2;
}seg[N];//竖线结构体
int cmp1(node s1,node s2)
{
    return s1.x<s2.x;
}
int k1;
struct P
{
    int x,y;
    int type;
}point[N*2];//点结构体
int cmp2(P l1,P l2)
{
    if(l1.x==l2.x)
        return l1.type<l2.type;
    return l1.x<l2.x;
}
int k2;
int num[N*2];
int k3;
int getInd(int y)//由实际值得到离散值
{
    return lower_bound(num,num+total,y)-num+1;
}
int main()
{
    int t;
    int x1,x2,y1,y2;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        memset(c,0,sizeof(c));
        k1=k2=k3=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            if(x1==x2)//竖线
            {
                num[k3++]=y1;
                num[k3++]=y2;//只离散y值
                if(y1>y2)
                {
                    int temp=y1;
                    y1=y2;
                    y2=temp;
                }
                seg[k1].x=x1;
                seg[k1].y1=y1;
                seg[k1].y2=y2;
                k1++;
            }
            else
            {
                num[k3++]=y1;
                if(x1>x2)
                {
                    int temp=x1;
                    x1=x2;
                    x2=temp;
                }
                point[k2].x=x1;
                point[k2].y=y1;
                point[k2].type=0;//把横线给拆掉
                k2++;
                point[k2].x=x2;
                point[k2].y=y1;
                point[k2].type=1;
                k2++;
            }
        }
        sort(seg,seg+k1,cmp1);
        sort(point,point+k2,cmp2);
        sort(num,num+k3);//各自的排序
        total=unique(num,num+k3)-num;
        long long ans=0;
        for(int i=0,j=0;i<k1;i++)//枚举竖线
        {
            while(j<k2&&(point[j].x<seg[i].x||(point[j].x==seg[i].x&&point[j].type==0)))//把所有横坐标小于竖线的横坐标的点的y值更新到树状数组
            {
                if(point[j].type==0)
                    change(getInd(point[j].y),1);
                else
                    change(getInd(point[j].y),-1);
                j++;
            }
            ans+=sum(getInd(seg[i].y2))-sum(getInd(seg[i].y1)-1);//统计答案
        }
        printf("%lldn",ans);
    }
    return 0;
}