No.2173 Nightcord
tko919
nok0Problem Statement
There are $N$ stars at distinct positions in the sky, which is represented as a two-dimensional plane.
The $i(1 \leq i\leq N)$-th star is at position $(X_i,Y_i)$, and its color is red if $C_i=1$ and blue if $C_i=2$.
A collection consisting of exactly $K$ of the $N$ stars and containing at least $1$ star of each color, red and blue, is called a "constellation".
Furthermore, a constellation is specifically called a "good constellation" if there does not exist a line that separates the red stars and the blue stars contained in it.
However, if a star forming the constellation lies on the line, the line is not considered to separate them.
Determine whether a good constellation exists.
Input
$N\ K$ $X_1\ Y_1\ C_1$ $\vdots$ $X_N\ Y_N\ C_N$
- $3 \leq K \leq N \leq 3000$
- $0 \leq |X_i|,|Y_i| \leq 10^9\ (1 \leq i \leq N)$
- If $i \neq j$, then $(X_i,Y_i) \neq (X_j,Y_j)$
- $C_i \in \{1,2\}\ (1 \leq i \leq N)$
- All input values are integers
Output
Print Yes if a good constellation exists, and No otherwise.
Sample
Sample 1
Input
4 3 0 0 1 0 1 2 1 2 1 2 0 2
Output
No
For example, the constellation consisting of stars $2,3,4$ is separated into red stars and blue stars by the line $y=\frac{3}{2}$.
Sample 2
Input
4 3 0 0 1 0 1 2 0 2 1 2 0 1
Output
Yes
One example of a good constellation is the one consisting of stars $1,2,3$.
Note that the collection of stars $1,3,4$ is not a constellation because all of its stars are red, and that for the constellation consisting of stars $1,2,3$, the line $x=0$ is not regarded as separating the $2$ colors.
Sample 3
Input
5 4 -8 -31 2 2 10 2 1 -27 1 4 30 2 -8 27 1
Output
Yes
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。