https://codeforc.es/contest/1194/problem/E

For 5000 normal (same direction will not overlap, nor degenerate into point) line segments, they are all parallel to the coordinate axis direction, to find how many rectangles can be formed.

Firstly, coordinate migration is carried out, which is classified according to horizontal line and vertical line.

With the idea of scanning line, start from the horizontal line at the bottom, mark all the vertical lines intersecting with the horizontal line, join the queue, and sort the vertical lines by y.

First undo the ending vertical line, and then start from the next horizontal line B of this horizontal line A, and ask how many marked vertical lines there are in the interval covered by line B.

Note that you can either offset 5001 or add a special judgment to the interval query. Prevent crossing to - 1.

Slow code.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 10001;
int bit[MAXN + 5];

inline int prefix_sum(int x) {
    int res = 0;
    for(; x; x -= x & -x)
        res += bit[x];
    return res;
}

inline void add(int x, int v) {
    for(; x <= MAXN; x += x & -x)
        bit[x] += v;
}

inline int range_sum(int l, int r) {
    return prefix_sum(r) - prefix_sum(l - 1);
}

struct Vertical_Line {
    int x, y1, y2;
    bool operator<(const Vertical_Line& vl) {
        return x != vl.x ? x < vl.x : y1 < vl.y1;
    }
} vl[5005];
int  vtop;

struct Vertical_Line_End {
    int x, y;
    bool operator<(const Vertical_Line_End& vle) {
        return y < vle.y;
    }
} vle[5005];
int vle_back, vle_front;

struct Horizontal_Line {
    int x1, x2, y;
    bool operator<(const Horizontal_Line& hl) {
        return y != hl.y ? y < hl.y : x1 < hl.x1;
    }
} hl[5005];
int htop;

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
    //freopen("Yinku.out", "w", stdout);
#endif // Yinku
    int n;
    while(~scanf("%d", &n)) {
        vtop = 0, htop = 0;
        int x1, y1, x2, y2;
        for(int i = 1; i <= n; i++) {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            x1 += 5001, y1 += 5001, x2 += 5001, y2 += 5001;
            if(x1 > x2)
                swap(x1, x2);
            if(y1 > y2)
                swap(y1, y2);
            if(x1 == x2) {
                ++vtop;
                vl[vtop].x = x1;
                vl[vtop].y1 = y1;
                vl[vtop].y2 = y2;
            } else {
                ++htop;
                hl[htop].y = y1;
                hl[htop].x1 = x1;
                hl[htop].x2 = x2;
            }
        }
        sort(vl + 1, vl + 1 + vtop);
        sort(hl + 1, hl + 1 + htop);
        ll ans = 0;
        for(int hi = 1; hi <= htop; hi++) {
            vle_front = 1;
            vle_back = 0;
            for(int vi = 1; vi <= vtop; vi++) {
                if(vl[vi].x >= hl[hi].x1 && vl[vi].x <= hl[hi].x2 && vl[vi].y1 <= hl[hi].y && vl[vi].y2 >= hl[hi].y) {
                    add(vl[vi].x, 1);
                    ++vle_back;
                    vle[vle_back].x = vl[vi].x;
                    vle[vle_back].y = vl[vi].y2;
                }
            }
            sort(vle + 1, vle + 1 + vle_back);
            int cury = hl[hi].y;
            for(int hii = hi + 1; hii <= htop; hii++) {
                while(vle_front <= vle_back && vle[vle_front].y < hl[hii].y) {
                    add(vle[vle_front].x, -1);
                    vle_front++;
                }
                int tmp = range_sum(hl[hii].x1, hl[hii].x2);
                ans += (tmp * (tmp - 1) >> 1);
            }
            while(vle_front <= vle_back) {
                add(vle[vle_front].x, -1);
                vle_front++;
            }
        }
        printf("%lld\n", ans);
    }
}

In fact, in the beginning, the vertical line is also sorted by y, which eliminates the later sorting. A little bit faster.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 10001;
int bit[MAXN + 5];

inline int prefix_sum(int x) {
    int res = 0;
    for(; x; x -= x & -x)
        res += bit[x];
    return res;
}

inline void add(int x, int v) {
    for(; x <= MAXN; x += x & -x)
        bit[x] += v;
}

inline int range_sum(int l, int r) {
    return prefix_sum(r) - prefix_sum(l - 1);
}

struct Vertical_Line {
    int x, y1, y2;
    bool operator<(const Vertical_Line& vl) {
        return y2 < vl.y2;
    }
} vl[5005];
int  vtop;

struct Vertical_Line_End {
    int x, y;
} vle[5005];
int vle_back, vle_front;

struct Horizontal_Line {
    int x1, x2, y;
    bool operator<(const Horizontal_Line& hl) {
        return y != hl.y ? y < hl.y : x1 < hl.x1;
    }
} hl[5005];
int htop;

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
    //freopen("Yinku.out", "w", stdout);
#endif // Yinku
    int n;
    while(~scanf("%d", &n)) {
        vtop = 0, htop = 0;
        int x1, y1, x2, y2;
        for(int i = 1; i <= n; i++) {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            x1 += 5001, y1 += 5001, x2 += 5001, y2 += 5001;
            if(x1 > x2)
                swap(x1, x2);
            if(y1 > y2)
                swap(y1, y2);
            if(x1 == x2) {
                ++vtop;
                vl[vtop].x = x1;
                vl[vtop].y1 = y1;
                vl[vtop].y2 = y2;
            } else {
                ++htop;
                hl[htop].y = y1;
                hl[htop].x1 = x1;
                hl[htop].x2 = x2;
            }
        }
        sort(vl + 1, vl + 1 + vtop);
        sort(hl + 1, hl + 1 + htop);
        ll ans = 0;
        for(int hi = 1; hi <= htop; hi++) {
            vle_front = 1;
            vle_back = 0;
            for(int vi = 1; vi <= vtop; vi++) {
                if(vl[vi].x >= hl[hi].x1 && vl[vi].x <= hl[hi].x2 && vl[vi].y1 <= hl[hi].y && vl[vi].y2 >= hl[hi].y) {
                    add(vl[vi].x, 1);
                    ++vle_back;
                    vle[vle_back].x = vl[vi].x;
                    vle[vle_back].y = vl[vi].y2;
                }
            }
            //sort(vle + 1, vle + 1 + vle_back);
            int cury = hl[hi].y;
            for(int hii = hi + 1; hii <= htop; hii++) {
                while(vle_front <= vle_back && vle[vle_front].y < hl[hii].y) {
                    add(vle[vle_front].x, -1);
                    vle_front++;
                }
                int tmp = range_sum(hl[hii].x1, hl[hii].x2);
                ans += (tmp * (tmp - 1) >> 1);
            }
            while(vle_front <= vle_back) {
                add(vle[vle_front].x, -1);
                vle_front++;
            }
        }
        printf("%lld\n", ans);
    }
}