Hide

Problem H
しわがれ声な馬

Languages en ja
/problems/hoarsehorses/file/statement/ja/img-0001.jpg
Picture by Alistair Hamilton via Flickr.

ボブの馬はすべてしわがれ声で、おそらく風邪をひいている。ポニーでさえもしわがれ声だ!そのため、すべての動物を隔離する必要がある。 動物を隔離するために、ボブは $n$ 個のフェンスを持っている。不幸なことに、アリスがボブのフェンスを適当に置いてしまった。ボブはこれらを置きなおす時間はないので、それらはそのままにしておかなければならない。

あなたには、ボブを手伝って隔離できる動物の数を計算してほしい。 すなわち、フェンスに囲まれ、空でない領域に動物を配置したい。そうすることで、どの動物も他の動物に近づくことができないし、逃げることもできなくなる。

各フェンスは2点間の線分として表される。また、$3$つのフェンスが同じ点を通ることはないと仮定する。フェンスはお互いに交差しても構わない。

入力

  • 先頭行は $1 \leq n \leq 1000$ の整数で、フェンスの数を表す。

  • その後 $n$ 行は $-{10}^9 \leq x_1, y_1, x_2, y_2 \leq {10}^9$$4$つの整数で、フェンスの両端の座標を表す。各フェンスは、両端の点を結ぶ線分として表される。

出力

単一の整数 $c$ を出力する。これは、ボブが隔離できる動物の数を表す。

\includegraphics[width=.4\textwidth ]{./sample-testcase3.pdf}
図 1: Illustration of the third example input.
サンプル入力 1 サンプル出力 1
1
1 1 1 2
0
サンプル入力 2 サンプル出力 2
4
1 0 1 5
4 0 4 5
0 1 5 1
0 4 5 4
1
サンプル入力 3 サンプル出力 3
5
1 0 1 5
4 0 4 5
0 1 5 1
0 4 5 4
-1 0 5 5
4