問題一覧 > 通常問題

No.2353 Guardian Dogs in Spring

レベル : / AI推定難易度 : 800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 145
作問者 : 👑 AngrySadEight / テスター : kumakuma Shirotsume 👑 seekworser
お気に入りにしたユーザー ProblemId : 9391 / 自分の提出
問題文最終更新日: 2023-05-12 09:54:42
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$ guardian dogs on the $xy$-plane. The $i(1 \leq i \leq N)$-th guardian dog is at coordinates $(x_i, y_i)$, and initially all guardian dogs face the positive direction of the $x$-axis.

Two guardian dogs form a pair of guardian dogs facing each other when the following conditions are satisfied.

  • Each of the two guardian dogs faces in the direction of the other.
  • When the two guardian dogs are connected by a line segment, no other guardian dog is on that segment.

You can freely change the direction of every guardian dog. Maximize the number of pairs of guardian dogs facing each other.

Constraints

  • All input values are integers.
  • $2 \leq N \leq 8000$
  • $0 \leq x_i, y_i \leq 8000$
  • $(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

Let $K$ be the number of pairs of guardian dogs facing each other, and output $K+1$ lines in the following format. That is,

  • On line $1$, output the number of pairs of guardian dogs facing each other.
  • On lines $2$ through $K+1$, output the pairs of indices $(z_1, w_1), (z_2, w_2), \dots, (z_K, w_K)$ of the guardian dogs facing each other, one pair per line.

$K$
$z_1$ $w_1$
$z_2$ $w_2$
$\cdots$
$z_K$ $w_K$

Sample

Sample 1
Input
3
1 1
2 1
3 2
Output
1
1 2

Below, the $i$-th guardian dog is referred to as "guardian dog $i$".

The placement of the guardian dogs and the directions they are made to face are as shown in the figure below.

If guardian dog $1$ and guardian dog $2$ are arranged to face each other, $1$ pair of guardian dogs facing each other is formed, and this is the maximum.

The remaining guardian dog $3$ can also be made to face in the direction of guardian dog $2$, but note that this does not form a pair of guardian dogs facing each other, because guardian dog $2$ is not facing in the direction of guardian dog $3$.

Sample 2
Input
4
1 1
2 2
3 3
4 2
Output
2
1 4
2 3

The placement of the guardian dogs and the directions they are made to face are as shown in the figure below.

If guardian dog $1$ and guardian dog $4$, and guardian dog $2$ and guardian dog $3$, are arranged to face each other, $2$ pairs of guardian dogs facing each other are formed, and this is the maximum.

On the other hand, an output such as the following is judged incorrect.

2
1 3
2 4

In this case, guardian dog $2$ is on the segment connecting guardian dog $1$ and guardian dog $3$, so the condition is no longer satisfied.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。