この問題は \(O(N^22^N)\) で答えを求めることができます。

まず、この問題に出てくる座標 \((A_{i}, B_{i}), (C_{i}, D_{i}), (0, 0)\) に適当なラベリングをし、それぞれ、頂点 \(0, 1, \dots, 2N\) とします。

\(dp[S][j]\) をもう引いた線分の集合を \(S\) であり、今いる頂点が \(j\) であるような引き方のうちの最短時間とします。

ここまでくると、 TSP と同じ bitDP で解くことができます。

c++ による実装例 1ms