問題一覧 > 通常問題

No.245 貫け!

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 86
作問者 : tubo28tubo28
3 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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。