## 分析

1. 扫描线第一次经过蛇的某端点
2. 扫描线第二次经过蛇的另一个端点（废话！）

## 代码

```#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define print(x) cout << x << endl
#define input(x) cin >> x

const int SIZE = 1024;

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

struct BITree {
int _tree[SIZE];
void init() {
memset(_tree, 0, sizeof(_tree));
}
void add(int x, int p) {
while (p < SIZE) {
_tree[p] += x;
p += lowbit(p);
}
}
int sum(int p) {
int res = 0;
while (p > 0) {
res += _tree[p];
p -= lowbit(p);
}
return res;
}
int sum(int a, int b) {
return sum(b) - sum(a - 1);
}
};

struct Point { int x, y; };
struct Snake { Point start, end; };

class Solution { // manual tested
public:
int count_intersection(const vector<Snake>& xsnakes,
const vector<Snake>& ysnakes) {
int ans = 0;
_tree.init();
vector<Mark> vec;
for (auto s: xsnakes) {
vec.push_back(Mark({s.start.x, 1, s.start.y}));
vec.push_back(Mark({s.end.x,  -1, s.end.y}));
}
int p = 0;
for (auto s: ysnakes) {
vec.push_back(Mark({s.start.x, 0, p++}));
}
sort(vec.begin(), vec.end());
for (auto mark: vec) {
if (mark.type == 1) {
} else if (mark.type == -1) {
} else {
p = mark.val;
int a = ysnakes[p].start.y;
int b = ysnakes[p].end.y;
ans += _tree.sum(a, b);
}
}
return ans;
}
private:
struct Mark {
int pos, type, val;
friend bool operator < (const Mark& a, const Mark& b) {
return a.pos < b.pos;
}
};
BITree _tree;
};

int main() {
vector<Snake> xsnakes({
Snake({ Point({1, 2}), Point({5, 2}) })
});
vector<Snake> ysnakes({
Snake({ Point({2, 1}), Point({2, 3}) }),
Snake({ Point({3, 1}), Point({3, 3}) })
});
Solution S;
print(S.count_intersection(xsnakes, ysnakes));
return 0;
}
```

《算法引论》