← 返回题目列表

Codeforces · 1270/E

E. 划分点

中文机器翻译题面 查看原题

给你一组 $$$n\ge 2$$$ 成对的具有整数坐标的不同点。您的任务是将这些点划分为两个非空组 $$$A$$$ 和 $$$B$$$,使得以下条件成立:

对于每两个点 $$$P$$$ 和 $$$Q$$$,将它们之间的欧氏距离写在黑板上:如果它们属于同一组 - 用黄色笔,如果它们属于不同组 - 用蓝色笔。那么没有黄色数字等于任何蓝色数字。

保证任何可能的输入都存在这样的分区。如果存在多个分区,则可以输出任意一个。

输入

第一行包含一个整数 $$$n$$$ $$$(2 \le n \le 10^3)​​$$$ — 点数。

接下来的 $$$n$$$ 行的第 $$$i$$$ 包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$-10^6 \le x_i, y_i \le 10^6$$$) — 第 $$$i$$$ 点的坐标。

保证所有 $$$n$$$ 点都是两两不同的。

输出

在第一行中,输出 $$$a$$$ ($$$1 \le a \le n-1$$$) — 组 $$$A$$$ 中的点数。

在第二行中,输出 $$$a$$$ 整数 — 包含在 $$$A$$$ 组中的点的索引。

如果有多个答案,请打印其中一个。

示例

输入 #1

3
0 0
0 1
1 0

输出 #1

1
1

输入 #2

4
0 1
0 -1
1 0
-1 0

输出 #2

2
1 2

输入 #3

3
-2 1
1 1
-1 0

输出 #3

1
2

输入#4

6
2 5
0 3
-4 -1
-5 -4
1 0
3 -1

输出#4

1
6

输入 #5

2
-1000000 -1000000
1000000 1000000

输出 #5

1
1

注意

在第一个示例中,我们将点 $$$(0, 0)$$$ 设置为组 $$$A$$$,将点 $$$(0, 1)$$$ 和 $$$(1, 0)$$$ 设置为组 $$$B$$$。这样,黑板上就会有$$$1$$$黄色数字$$$\sqrt{2}$$$和$$$2$$$蓝色数字$$$1$$$。

在第二个示例中,我们将点 $$$(0, 1)$$$ 和 $$$(0, -1)$$$ 设置为组 $$$A$$$,将点 $$$(-1, 0)$$$ 和 $$$(1, 0)$$$ 设置为组 $$$B$$$。这样,黑板上就会有$$$2$$$黄色数字$$$2$$$,$$$4$$$蓝色数字$$$\sqrt{2}$$$。