No.461

線分は $p_i$ でグループ分けしておく.

各グループから1本ずつ取ってきた3本の線分が大きな三角形の中で三角形を作れるかどうかを考える.

まず, 3本が1点で交わってはいけない.

まず, $c_i = b_i / (a_i + b_i)$ とおき, 頂点0,1を結ぶ辺のベクトルを $v_1$, 頂点0,2を結ぶ辺のベクトルを $v_2$ とおくと, 頂点0の対辺に平行な線分と頂点1の対辺に平行な線分の交点の位置ベクトルは,

$$c_1v_1 + (1-c_0-c_1)v_2$$

となり, 頂点0の対辺に平行な線分と頂点2の対辺に平行な線分の交点の位置ベクトルは,

$$c_2v_2 + (1-c_0-c_2)v_2$$

となる. これが一致するということは,

$$c_1 = 1-c_0-c_2$$

ということであり,

$$c_0+c_1+c_2 = 1$$

を得る.

次に3本のうち2本が三角形の内部で交わらなければいけないという条件だが, これは,

$$1-c_0-c_1 \geq 0$$

ということであり, ここから

$$c_0+c_1 \leq 1$$

を得る.

これをすべての組み合わせで試すと $O(N^3)$ の計算量が必要になるので TLE である.

そこで, 2本を決めて $c_0, c_1$ が決まれば, $c_2$ の範囲が決まるので, $c_2$ をソートしておけば二分探索で求めることができる.

なお, $c_i$ は分数で持っておく. 分母分子に出てくる数値は最大でも $(a_i+b_i)^3$ なので, 分母分子は long でもっておけば約分の必要はない.