http://codeforces.com/contest/1270/problem/E

题意：二维平面给出一些点，要求把这些点分成两组，任何不同组的两个点的欧式距离不能与任何同组的两个点的欧式距离相等。

奇偶分类构造

本题并不要求欧式距离估算出浮点数。例如 2\sqrt 2 不需要写成 1.414。所以欧式距离不同等价于欧式距离的平方不同，因此以下只讨论平方。

先把所有点分成4类，x，y分别为 {奇偶，偶奇，奇奇，偶偶}，则同一类的两个点欧式距离平方一定为偶数。对于不同组的，奇偶和偶奇，奇奇和偶偶也是偶数。所以只要把所有点各自分到四类中去，就自然组间距离为奇数，组内距离为偶数，也就不同了。

  1. 如果有3组或4组，可以直接按以上标准分类。

  2. 如果有2组，这两组组间距离可能还是偶数，但此时组间与组内距离绝对不同，因为组内是两个偶数的平方和，是4的倍数。组间是两个奇数的平方和，模4为2。所以直接把这两类分开即可。

  3. 如果只有1组，就把每个点坐标除以2，相当于距离都缩小了4，并不影响其是否相等，却可能改变其坐标的奇偶性，而产生新的分组。

由于奇数除2会有精度问题，所以在除2之前确保不存在一奇一偶除2结果相同的情况是必要的，所以要先把所有情况都判断完了再除2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int n;
int x[maxn], y[maxn];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d%d", &x[i], &y[i]);
	for (;;) {
		int cnt = 0;
		for (int i = 1; i <= n; i++)if ((x[i] & 1) ^ (y[i] & 1))cnt++;
		if (cnt > 0 && cnt < n) {
			printf("%d\n", cnt);
			for (int i = 1; i <= n; i++)if ((x[i] & 1) ^ (y[i] & 1))printf("%d ",i);
			printf("\n");
			return 0;
		}
		else {
			int tmp = 0;
			for (int i = 1; i <= n; i++)if (x[i] & 1)tmp++;
			if (tmp > 0 && tmp < n) {
				printf("%d\n", tmp);
				for (int i = 1; i <= n; i++)if (x[i] & 1)printf("%d ", i);
				printf("\n");
				return 0;
			}
		}
		for (int i = 1; i <= n; i++) { x[i] >>= 1; y[i] >>= 1; }
	}
	return 0;
}