原题链接
曼波~
\(n^2\) 过百万，暴力踩标算。
实则是不是百万。
思路
注意到输入范围最后一行，表示每次询问两个起冲突的部落是一定互不相同的（当然即使相同也可以记忆化），那么每次询问对两个部落之间的龙进行暴力枚举枚举是均摊 \(O(n^2)\) 的，与 \(q\) 无关。题目中 \(n\) 的范围是 \(30000\)，卡卡常能过。
对于验证每一条龙向另一条龙发射火球是否会破坏道路，显然可以转换为验证射线与线段是否相交，是计算几何板子。
卡常
挺好卡的，把计算几何的板子加点 inline 然后用链式前向星就很快了。虽然我卡了很久。
部分代码
const int maxn = 3 * 1e4 + 1;int n, m, q, ans = 0, tot, id, res, head[maxn];
struct edge {pair <int, int> p;int nxt;
} e[maxn];
pair <int, int> x, y;// 为了卡常其他的都可以开 int，但计算几何板子里面一定开开 long long。
#define pii pair <long long, long long>
inline pii to(pii a, pii b) { return {b.first - a.first, b.second - a.second}; }
inline long long cj(pii a, pii b) { return a.first * b.second - b.first * a.second; }
inline bool getdirection(pii a, pii b, pii c) { return cj(to(a, b), to(a, c)) > 0; }
inline int check(pii f, pii t, pii a, pii b) { return getdirection(a, b, f) ? (!getdirection(a, f, t) && getdirection(b, f, t)) : (getdirection(a, f, t) && !getdirection(b, f, t)); }void solve() {cin >> n >> m;for(int i = 1, from; i <= n; i++) {pair <int, int> p;cin >> p.first >> p.second >> from;tot++;e[tot].p = p, e[tot].nxt = head[from];head[from] = tot;}cin >> x.first >> x.second >> y.first >> y.second >> q;while(q--) {int id1, id2;cin >> id1 >> id2;res = 0;for(int i1 = head[id1]; i1; i1 = e[i1].nxt) for(int i2 = head[id2]; i2; i2 = e[i2].nxt) res += check(e[i1].p, e[i2].p, x, y);cout << res; el;}
}