HDU - 5862 Counting Intersections——线段树+扫描线

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int maxn = 2e5 + 10;
int T, n, len;
long long ans;
struct Segment { int x1, y1, x2, y2; } seg[maxn];
vector<int> vx, vy;
map<int, int> idx, idy;
int m;
struct Line {
    vector<pair<int, int>> l;
    vector<int> s;
    vector<int> t;
}line[maxn];
struct Segmenttree {
    int sum[maxn<<2];
    void build() { for (int i = 1; i <= (len<<2); i++) sum[i] = 0; }
    void pushup(int root) { sum[root] = sum[root<<1] + sum[root<<1|1]; }
    void update(int l, int r, int root, int p, int v) {
        if (l == r) { sum[root] += v; return; }
        int mid = (l + r) >> 1;
        if (p <= mid) update(l, mid, root<<1, p, v);
        else update(mid + 1, r, root<<1|1, p, v);
        pushup(root);
    }
    int query(int l, int r, int root, int ql, int qr) {
        if (ql <= l && r <= qr) return sum[root];
        int mid = (l + r) >> 1;
        int ans = 0;
        if (ql <= mid) ans += query(l, mid, root<<1, ql, qr);
        if (mid < qr) ans += query(mid + 1, r, root<<1|1, ql, qr);
        return ans;
    }
}ac;
int witch(Segment &s) { return s.x1 == s.x2; }
void init() {
    vx.clear(); vy.clear();
    idx.clear(); idy.clear();
    for (int i = 1; i <= n; i++) {
        if (!witch(seg[i])) {
            vx.push_back(seg[i].x1); vx.push_back(seg[i].x2);
            vy.push_back(seg[i].y1);
        }
        else {
            vx.push_back(seg[i].x1);
            vy.push_back(seg[i].y1); vy.push_back(seg[i].y2);
        }
    }
    sort(vx.begin(), vx.end());
    len = unique(vx.begin(), vx.end()) - vx.begin();
    for (int i = 0; i < len; i++) idx[vx[i]] = i + 1;
    sort(vy.begin(), vy.end());
    m = unique(vy.begin(), vy.end()) - vy.begin();
    for (int i = 0; i < m; i++) idy[vy[i]] = i + 1;
    for (int i = 1; i <= m; i++) {
        line[i].l.clear();
        line[i].s.clear();
        line[i].t.clear();
    }
    for (int i = 1; i <= n; i++) {
        if (!witch(seg[i])) line[idy[seg[i].y1]].l.push_back(make_pair(idx[seg[i].x1], idx[seg[i].x2]));
        else {
            line[idy[seg[i].y1]].s.push_back(idx[seg[i].x1]);
            line[idy[seg[i].y2]].t.push_back(idx[seg[i].x1]);
        }
    }
}
void solve() {
    ans = 0;
    ac.build();
    for (int i = 1; i <= m; i++) {
        for (unsigned int j = 0; j < line[i].s.size(); j++) ac.update(1, len, 1, line[i].s[j], 1);
        if (!line[i].l.empty()) {

            for (unsigned int j = 0; j < line[i].l.size(); j++) {
                ans += ac.query(1, len, 1, line[i].l[j].first, line[i].l[j].second);
            }
        }
        for (unsigned int j = 0; j < line[i].t.size(); j++) ac.update(1, len, 1, line[i].t[j], -1);
    }
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d%d%d", &seg[i].x1, &seg[i].y1, &seg[i].x2, &seg[i].y2);
            if (seg[i].x1 > seg[i].x2) swap(seg[i].x1, seg[i].x2);
            if (seg[i].y1 > seg[i].y2) swap(seg[i].y1, seg[i].y2);
        }
        init();
        solve();
        printf("%lldn", ans);
    }
    return 0;
}