No.245 Pierce Through!
レベル :
/ AI推定難易度 : 1650
/ 実行時間制限 : 1ケース 5.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 87
作問者 :
tubo28
タグ : / 解いたユーザー数 87
作問者 :
tubo28
問題文最終更新日: 2026-06-26 23:28:17
English (AI translation)
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.
- 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もしくは右上の雲マークをクリックしてアカウントを作成してください。