Segment Set - Segment Intersections: Manhattan Geometry

Time Limit : 2 sec, Memory Limit : 65536 KB

線分交差(マンハッタン幾何)

$x$ 軸または $y$ 軸に平行な $n$ 本の線分が与えられるので、それらの交点の数を出力してください。

入力

1行目に線分の数 $n$ が与えられます。続く $n$ 行に $n$ 本の線分が与えられます。各線分は次の形式で与えられます。

$x_1 \; y_1 \; x_2 \; y_2$

これらは線分の端点のそれぞれの座標です。入力はすべて整数で与えられます。

出力

交点の数を1行に出力してください。

制約

  • $1 \leq n \leq 100,000$
  • $ -1,000,000,000 \leq x_1, y_1, x_2, y_2 \leq 1,000,000,000$
  • 互いに平行な2つ以上の線分が、線分あるいは点で重なることはない。
  • 交点の数は $1,000,000$ を超えない。

入力例 1

6
2 2 2 5
1 3 5 3
4 1 4 4
5 2 7 2
6 1 6 3
6 5 6 7

出力例 1

3

Note

      解説