No.245 貫け!

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 69
作問者 : tubo28tubo28
1 ProblemId : 507 / 出題時の順位表
問題文最終更新日: 2017-02-13 22:39:25

問題文

平面上に $N$ 個の線分があります。
あなたはそこに $1$ つ好きに直線を引くことができます。
最大で何本の線分と交わるようにできるか求めてください。

この問題において、直線と線分が交わるとは、
両方に共通して含まれる点(端点を含む)が $1$ 個以上存在することとします。

入力

$N$
$a_1$ $b_1$ $c_1$ $d_1$
$\vdots$
$a_N$ $b_N$ $c_N$ $d_N$

$1$ 行目に $N$ が与えられます。
$1+i$ 行目には $i$ 番目の線分の端点 $(a_i, b_i),(c_i,d_i)$ が与えられます。

以下の制約を満たします。
  • 全て整数
  • $1 \leq N \leq 100$
  • $|a_i|,|b_i|,|c_i|,|d_i| \leq 100$
  • $(a_i, b_i) \neq (c_i, d_i)$
  • $i \neq j$ なら $(a_i, b_i, c_i, d_i) \neq (a_j, b_j, c_j, d_j), (c_j, d_j, a_j, b_j)$

出力

答えを $1$ 行で出力し、最後に改行を出力してください。

サンプル

サンプル1
入力
2
0 0 1 0
0 1 1 1
出力
2

サンプル2
入力
4
0 0 1 0
1 0 2 0
0 1 1 1
1 1 2 1
出力
4

サンプル3
入力
4
0 0 1 0
2 0 3 0
0 1 1 1
2 1 3 1
出力
2

サンプル4
入力
2
0 0 1 0
2 0 3 0
出力
2

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。