Counting Intersections HDU - 5862 (离散化+树状数组扫描线段)

98 阅读 0 评论 65 点赞

我是靠谱客的博主机智黄豆，这篇文章主要介绍Counting Intersections HDU - 5862 (离散化+树状数组扫描线段)，现在分享给大家，希望可以做个参考。

题目来源：Counting Intersections

题意

给你n条与坐标轴平行的线段，问有几个交点。数据保证没有重合的、长度为0的线段，没有共起点共终点的线段。

思路

由于所有线段都是和坐标轴平行的，所以可以把与x轴平行的线段和y轴平行的线段分开来看，将横着的线段纵坐标插入树状数组中，求所有竖着的线段起点到终点的区间和即为答案。求解的过程需要按照横坐标从小到大排序，横线段的点优先。

由于题目说明点的坐标绝对值是小于1e9的，需要将纵坐标离散化。可以使用stl中的sort，unique和lower_bound来实现从0开始的离散化。

离散化

复制代码

1
2
3
4
5
6
7
int t[N]; //t储存了所有需要离散的数据
int a[N]; //a是原始数据
sort(t, t + N);
int size = unique(t, t + N) - t;
for(int i = 0;i < N; ++i)
    a[i] = lower_bound(t, t + N, a[i]) - t;

代码

复制代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
const int N = 1000005;
int n;
long long cnt, cntY, many;
long long Y[N << 2];
struct node
{
    int type;
    long long pos, s, t;
    node() {}
    node(int _type, long long _pos, long long _s, long long _t) :type(_type), pos(_pos), s(_s), t(_t) {}
    bool operator<(const node x) const
    {
        if (pos == x.pos)
            return type < x.type;
        else
            return pos < x.pos;
    }
}e[N << 2];
namespace BIT
{
    long long tree[N << 2];
    inline int lb(int x) { return x & (~x + 1); }
    inline  long long sum(int x)
    {
        long long tot = 0;
        for (int i = x; i; i -= lb(i))  tot += tree[i];
        return tot;
    }
    inline void add(int x, long long v)
    {
        for (int i = x; i <= 4 * many; i += lb(i))  tree[i] += v;
    }
}
inline long long max(long long x, long long y) { return x > y ? x : y; }
inline long long min(long long x, long long y) { return x > y ? y : x; }
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        cnt = 0;
        cntY = 0;
        memset(BIT::tree, 0, sizeof(BIT::tree));
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
        {
            int x1, x2, y1, y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            if (y1 == y2)//横
            {
                if (x1 > x2)    std::swap(x1, x2);
                e[++cnt] = node(0, x1, y1, 1);
                e[++cnt] = node(0, x2 + 1, y2, -1);
            }
            else
                e[++cnt] = node(1, x1, min(y1, y2), max(y1, y2));
            Y[++cntY] = y1;
            Y[++cntY] = y2;
        }
        std::sort(Y + 1, Y + 1 + cntY);
        many = std::unique(Y + 1, Y + 1 + cntY) - Y - 1;
        for (int i = 1; i <= cnt; ++i)
        {
            if (e[i].type == 0)
                e[i].s = std::lower_bound(Y + 1, Y + 1 + many, e[i].s) - Y + 1;
            else
            {
                e[i].s = std::lower_bound(Y + 1, Y + 1 + many, e[i].s) - Y + 1;
                e[i].t = std::lower_bound(Y + 1, Y + 1 + many, e[i].t) - Y + 1;
            }
        }
        std::sort(e + 1, e + 1 + cnt);

long long ans = 0;
        for (int i = 1; i <= cnt; ++i)
        {
            if (e[i].type == 0)
                BIT::add(e[i].s, e[i].t);
            else
                ans += BIT::sum(e[i].t) - BIT::sum(e[i].s - 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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
const int N = 1000005;
int n;
long long cnt, cntY, many;
long long Y[N << 2];
struct node
{
    int type;
    long long pos, s, t;
    node() {}
    node(int _type, long long _pos, long long _s, long long _t) :type(_type), pos(_pos), s(_s), t(_t) {}
    bool operator<(const node x) const
    {
        if (pos == x.pos)
            return type < x.type;
        else
            return pos < x.pos;
    }
}e[N << 2];
namespace BIT
{
    long long tree[N << 2];
    inline int lb(int x) { return x & (~x + 1); }
    inline  long long sum(int x)
    {
        long long tot = 0;
        for (int i = x; i; i -= lb(i))  tot += tree[i];
        return tot;
    }
    inline void add(int x, long long v)
    {
        for (int i = x; i <= 4 * many; i += lb(i))  tree[i] += v;
    }
}
inline long long max(long long x, long long y) { return x > y ? x : y; }
inline long long min(long long x, long long y) { return x > y ? y : x; }
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        cnt = 0;
        cntY = 0;
        memset(BIT::tree, 0, sizeof(BIT::tree));
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
        {
            int x1, x2, y1, y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            if (y1 == y2)//横
            {
                if (x1 > x2)    std::swap(x1, x2);
                e[++cnt] = node(0, x1, y1, 1);
                e[++cnt] = node(0, x2 + 1, y2, -1);
            }
            else
                e[++cnt] = node(1, x1, min(y1, y2), max(y1, y2));
            Y[++cntY] = y1;
            Y[++cntY] = y2;
        }
        std::sort(Y + 1, Y + 1 + cntY);
        many = std::unique(Y + 1, Y + 1 + cntY) - Y - 1;
        for (int i = 1; i <= cnt; ++i)
        {
            if (e[i].type == 0)
                e[i].s = std::lower_bound(Y + 1, Y + 1 + many, e[i].s) - Y + 1;
            else
            {
                e[i].s = std::lower_bound(Y + 1, Y + 1 + many, e[i].s) - Y + 1;
                e[i].t = std::lower_bound(Y + 1, Y + 1 + many, e[i].t) - Y + 1;
            }
        }
        std::sort(e + 1, e + 1 + cnt);

        long long ans = 0;
        for (int i = 1; i <= cnt; ++i)
        {
            if (e[i].type == 0)
                BIT::add(e[i].s, e[i].t);
            else
                ans += BIT::sum(e[i].t) - BIT::sum(e[i].s - 1);
        }
        printf("%lldn", ans);
    }
    return 0;
}