問題一覧 > 通常問題

No.245 Pierce Through!

レベル : / AI推定難易度 : 1650 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 87
作問者 : tubo28
お気に入りにしたユーザー ProblemId : 507 / 自分の提出
問題文最終更新日: 2026-06-26 23:28:17
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 115 (順位表) の他の問題:

Problem Statement

There are $N$ line segments on a plane.
You may draw $1$ straight line anywhere you like.
Find the maximum number of line segments it can intersect.

In this problem, a line and a line segment are said to intersect if
there exists at least $1$ point (endpoints included) contained in both of them.

Input

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

Line $1$ contains $N$.
Line $1+i$ contains the endpoints $(a_i, b_i),(c_i,d_i)$ of the $i$-th line segment.

The following constraints are satisfied.
  • All values are integers
  • $1 \leq N \leq 100$
  • $|a_i|,|b_i|,|c_i|,|d_i| \leq 100$
  • $(a_i, b_i) \neq (c_i, d_i)$
  • If $i \neq j$, then $(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)$

Output

Output the answer on $1$ line, followed by a newline.

Sample

Sample 1
Input
2
0 0 1 0
0 1 1 1
Output
2

Sample 2
Input
4
0 0 1 0
1 0 2 0
0 1 1 1
1 1 2 1
Output
4

Sample 3
Input
4
0 0 1 0
2 0 3 0
0 1 1 1
2 1 3 1
Output
2

Sample 4
Input
2
0 0 1 0
2 0 3 0
Output
2

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