問題一覧 > ⚠未証明/不備あり問題

No.2180 Comprehensive Line Segments

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 3
作問者 : MasKoaTSMasKoaTS / テスター : 👑 potato167potato167 ShirotsumeShirotsume
1 ProblemId : 8509 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-01-12 12:14:40

追記(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もしくは右上の雲マークをクリックしてアカウントを作成してください。