問題一覧 > 通常問題

No.2355 Unhappy Back Dance

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 89
作問者 : 👑 AngrySadEight / テスター : kumakuma hikikomori
お気に入りにしたユーザー ProblemId : 9474 / 自分の提出
問題文最終更新日: 2023-05-14 11:45:32
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 393 (順位表) の他の問題:

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