No.2180 Comprehensive Line Segments
タグ : / 解いたユーザー数 3
作問者 : MasKoaTS / テスター : 👑 potato167 Shirotsume
追記(2023/1/7)
想定解に不備が見つかったため、本問を「未証明・不備あり問題」に設定いたしました。
皆様にご迷惑をおかけし、誠に申し訳ございません。
また、以下でご指摘いただいたケースをそれぞれ「09_after_contest_01.txt」「09_after_contest_02.txt」「09_after_contest_03.txt」として
テストケースに追加いたしました。ご指摘いただいたhamamu氏、toomer氏に感謝申し上げます。
https://twitter.com/hamamu_kyopro/status/1611608171348623361?s=20&t=AtIwoxqGveKWz41Jo_opRg
https://twitter.com/toomerhs/status/1611610210396942336?s=20&t=AtIwoxqGveKWz41Jo_opRg
https://twitter.com/toomerhs/status/1611614052224217089?s=20&t=AtIwoxqGveKWz41Jo_opRg
追記(2023/1/12)
本問における想定解の不備について、下記に詳細を纏めました。もしよろしければ、ご一読いただけると幸いです。
→ https://maskoats.hatenablog.com/entry/2023/01/12/115331
問題文
二次元平面上に $N$ 個の点 $P_{1}, P_{2}, \dots, P_{N}$ があり、点 $P_{i}$ $(1 \leq i \leq N)$
の座標は $( X_{i}, Y_{i} )$ です。
次の条件を満たす正整数 $n$ の最小値を求めてください。
この平面上に座標の重複を許して $n+1$ 個の点 $Q_{0}, Q_{1}, \dots, Q_{n}$ を適切に配置したとき、次が成り立つ。
任意の整数 $i$ $(1 \leq i \leq N)$ に対してある整数 $j$ $(1 \leq j \leq n)$ が存在し、
点 $P_{i}$ が線分 $Q_{j-1} Q_{j}$ (端点を含む)上にある。
制約
$1 \leq N \leq 12$
$-100 \leq X_{i}, Y_{i} \leq 100$ $(1 \leq i \leq N)$
$(X_{i}, Y_{i}) \neq (X_{j}, Y_{j})$ $(1 \leq i < j \leq N)$
入力はすべて整数
入力
入力は次の形式で与えられます。
$N$ $X_{1}$ $Y_{1}$ $X_{2}$ $Y_{2}$ $\vdots$ $X_{N}$ $Y_{N}$
$1$ 行目には $N$ が与えられる
$(1 + i)$ $(1 \leq i \leq N)$ 行目には $X_{i}$ と $Y_{i}$ がこの順に半角スペース区切りで与えられる
出力
答えを $1$ 行に出力してください。
サンプル
サンプル1
入力
6 0 0 2 0 3 1 2 2 0 2 -1 1
出力
3
例えば $n = 3$ として、$4$ 個の点の座標をそれぞれ
$Q_{0}(-2,0), Q_{1}(4,0), Q_{2}(1,3), Q_{3}(-2,0)$ とすれば良いです。
この場合、
点 $P_{1}, P_{2}$ はいずれも線分 $Q_{0} Q_{1}$ 上にある。
点 $P_{3}, P_{4}$ はいずれも線分 $Q_{1} Q_{2}$ 上にある。
点 $P_{5}, P_{6}$ はいずれも線分 $Q_{2} Q_{3}$ 上にある。
となります。
$n < 3$ のとき、条件を満たす点の配置方法は存在しません。
サンプル2
入力
4 3 1 0 0 5 -2 5 -5
出力
2
例えば $n = 2$ として、$3$ 個の点の座標をそれぞれ
$\displaystyle Q_{0} \left( -1, -\dfrac{1}{3} \right), Q_{1}\left( 5, \dfrac{5}{3} \right),
Q_{2} \left( 5, -5 \right)$ とすれば良いです。
配置する点の座標は整数でなくても構いません。
サンプル3
入力
1 -100 -100
出力
1
サンプル4
入力
12 5 55 4 49 -1 15 9 86 -2 10 -12 -59 2 40 7 76 10 98 -3 8 8 86 -6 -23
出力
6
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。