No.2355 Unhappy Back Dance
タグ : / 解いたユーザー数 89
作問者 : 👑
hikikomori
Problem Statement
There are $N$ dancers dancing on a two-dimensional coordinate plane. The $i(1 \leq i \leq N)$-th dancer is at coordinates $(X_i, Y_i)$, and initially all dancers face the positive direction of the $x$-axis.
A dancer is called an unhappy dancer if the following condition is satisfied.
- There are $2$ or more dancers exactly behind them. Specifically, when a half-line is drawn starting from the point where the dancer stands, in the direction opposite to the one they are facing, there are $2$ or more other dancers on the half-line.
When you can freely change the directions of the $N$ dancers, find the maximum number of unhappy dancers.
Constraints
- All inputs are integers.
- $1 \leq N \leq 1500$
- $0 \leq X_i, Y_i \leq 10^{18}$
- $(X_i, Y_i) \neq (X_j, Y_j) (i \neq j)$
Input
The input is given from standard input in the following format.
$N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\cdots$ $X_N$ $Y_N$
Output
Output the answer.
Sample
Sample 1
Input
4 1 1 2 2 3 3 1 3
Output
2
By choosing the directions of the dancers as shown below, at most $2$ dancers, the $1$-st dancer and the $3$-rd dancer, can be made unhappy dancers.
It is impossible to make $3$ or more dancers unhappy dancers.
Sample 2
Input
5 1 1 1 3 2 4 3 3 3 1
Output
0
No dancer can be made an unhappy dancer.
Sample 3
Input
9 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
Output
8
All dancers except the $5$-th dancer can be made unhappy dancers.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。