解説線分の内部が y=0y=0y=0 と交わるのは、両端の Y 座標の符号が異なる場合に限る。同符号なら線分全体が片側にあり、一方が 000 なら端点だけで交わる。両方が 000 の入力はない。したがって異符号の組を数える。時間計算量は O(∑N)O(\sum N)O(∑N)、追加領域は O(1)O(1)O(1)。単純解法として積 Y1,iY2,i<0Y_{1,i}Y_{2,i}<0Y1,iY2,i<0 を調べてもよい。積の絶対値は最大 101210^{12}1012 なので64ビット整数を使う。 Solution written by GPT6.1
