線分アレンジメント
概要
線分の集合を入力とし，任意の2線分の交点を頂点とし，頂点間に辺が存在する $\leftrightarrow$ 両方を含む線分が存在するという条件を満たすグラフを作ります．
実装
//@require intersection.cc
Graph segment_arrangement(const std::vector<L> &ss, std::vector<P> &ps) {
for (int i = 0; i < (int)ss.size(); ++i) { // O(n^2)
ps.push_back(ss[i][0]);
ps.push_back(ss[i][1]);
for (int j = i + 1; j < (int)ss.size(); ++j)
if (intersectSS(ss[i], ss[j])) ps.push_back(crosspointLL(ss[i], ss[j]));
}
std::sort(ps.begin(), ps.end());
ps.erase(std::unique(ps.begin(), ps.end()), ps.end());
Graph g(ps.size());
for (int i = 0; i < (int)ss.size(); ++i) {
std::vector<std::pair<double, int>> list;
for (int j = 0; j < (int)ps.size(); ++j)
if (intersectSP(ss[i], ps[j]))
list.push_back(std::make_pair(norm(ss[i][0] - ps[j]), j));
std::sort(list.begin(), list.end());
for (int j = 0; j + 1 < (int)list.size(); ++j) {
int a = list[j].second, b = list[j + 1].second;
Weight len = abs(ps[a] - ps[b]);
add_edge(g, a, b, len);
}
}
return g;
}