No.2180 Comprehensive Line Segments
タグ : / 解いたユーザー数 7
作問者 :
MasKoaTS
/ テスター :
👑 
Shirotsume
Addendum (2023/1/7)
Since a flaw was found in the intended solution, this problem has been designated as an "unproven / flawed problem".
We deeply apologize for the inconvenience caused to everyone.
In addition, the cases pointed out below have been added to the test cases as "09_after_contest_01.txt", "09_after_contest_02.txt", and "09_after_contest_03.txt", respectively.
We would like to thank hamamu and toomer for pointing them out.
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
Addendum (2023/1/12)
The details of the flaw in the intended solution of this problem are summarized at the link below. We would appreciate it if you could read it.
→ https://maskoats.hatenablog.com/entry/2023/01/12/115331
Problem Statement
There are $N$ points $P_{1}, P_{2}, \dots, P_{N}$ on a two-dimensional plane, and the coordinates of point $P_{i}$ $(1 \leq i \leq N)$ are $( X_{i}, Y_{i} )$.
Find the minimum positive integer $n$ satisfying the following condition.
It is possible to place $n+1$ points $Q_{0}, Q_{1}, \dots, Q_{n}$ on this plane, with coinciding coordinates allowed, so that the following holds.
For every integer $i$ $(1 \leq i \leq N)$, there exists an integer $j$ $(1 \leq j \leq n)$ such that point $P_{i}$ lies on the line segment $Q_{j-1} Q_{j}$ (including its endpoints).
Constraints
$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)$
All input values are integers.
Input
The input is given in the following format.
$N$
$X_{1}$ $Y_{1}$
$X_{2}$ $Y_{2}$
$\vdots$
$X_{N}$ $Y_{N}$
The $1$st line contains $N$.
The $(1 + i)$-th $(1 \leq i \leq N)$ line contains $X_{i}$ and $Y_{i}$ in this order, separated by a single space.
Output
Output the answer on $1$ line.
Sample
Sample 1
Input
6 0 0 2 0 3 1 2 2 0 2 -1 1
Output
3
For example, you can take $n = 3$ and set the coordinates of the $4$ points to $Q_{0}(-2,0), Q_{1}(4,0), Q_{2}(1,3), Q_{3}(-2,0)$, respectively.
In this case, the following holds:
Points $P_{1}, P_{2}$ both lie on the line segment $Q_{0} Q_{1}$.
Points $P_{3}, P_{4}$ both lie on the line segment $Q_{1} Q_{2}$.
Points $P_{5}, P_{6}$ both lie on the line segment $Q_{2} Q_{3}$.
That is all of the points.
When $n < 3$, there is no placement of points satisfying the condition.
Sample 2
Input
4 3 1 0 0 5 -2 5 -5
Output
2
For example, you can take $n = 2$ and set the coordinates of the $3$ points to
$\displaystyle Q_{0} \left( -1, -\dfrac{1}{3} \right), Q_{1}\left( 5, \dfrac{5}{3} \right),
Q_{2} \left( 5, -5 \right)$, respectively.
The coordinates of the placed points do not have to be integers.
Sample 3
Input
1 -100 -100
Output
1
Sample 4
Input
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
Output
6
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。