CF1270E Divide Points 做题记录

给你 $n$ 个点和它们的坐标，现在给它们两两连上边，如果在同一组为黄色，不同组为蓝色。现在让你给出任意一种分组方案，使得所有长度相同的边颜色相同。

$2 \le n \le 10^3$。

发现两点距离相等等价于两点的距离的平方相等，所以考虑距离的平方。

发现要把距离分成两组，不难想到奇偶性分类。设 $\operatorname{tpe}(x,y)=\begin{cases}0&x\equiv y\pmod2\\1&x\not\equiv y\pmod2\end{cases}$，由于 $(x1,y1),(x2,y2)$ 的距离的平方 $(x1-x2)^2+(y1-y2)^2$ 为奇数当且仅当 $\operatorname{tpe}(x1,y1)\not=\operatorname{tpe}(x2,y2)$，为偶数当且仅当 $\operatorname{tpe}(x1,y1)=\operatorname{tpe}(x2,y2)$，那么把 $\operatorname{tpe}(x,y)=0$ 的 $(x,y)$ 分到一组，$tpe(x,y)=1$ 的 $(x,y)$ 分到另一组即可。

但是发现 $\operatorname{tpe}(x,y)$ 有可能都为 $0$ 或者都为 $1$，考虑到平移对距离没有影响，所以当 $\operatorname{tpe}(x,y)=1$ 时让所有 $x$ 同时加上 $1$，这样就可以只讨论 $\operatorname{tpe}(x,y)=0$ 的情况。

注意到当 $\operatorname{tpe}(x,y)=0$ 时 $x+y\equiv x-y\equiv 0\pmod2$，所以有一个很奇妙的操作：旋转并拉伸坐标系。具体的，让 $(x,y)\to(\frac{x+y}{2},\frac{x-y}{2})$ 即让 $\begin{bmatrix}x\\y\end{bmatrix}\to\begin{bmatrix}x\\y\end{bmatrix}\times\begin{bmatrix}\frac{1}{2}&\frac{1}{2}\\\frac{1}{2}&-\frac{1}{2}\end{bmatrix}$，由于旋转操作最多进行 $\log V$ 次，所以这样可以在 $O(n\log V)$ 的时间复杂度内解决此题。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=100005;

struct node
{
	int x,y;
}a[S];

int n;
int tot,ans[S];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
	while(1)
	{
		tot=0;
		for(int j=1;j<=n;j++) if((a[j].x&1)==(a[j].y&1)) ans[++tot]=j;
		if(tot>=1&&tot<=n-1)
		{
			printf("%d\n",tot);
			for(int j=1;j<=tot;j++) printf("%d ",ans[j]);
			printf("\n");
			break;
		} 
		for(int j=1;j<=n;j++)
		{
			if((a[j].x&1)!=(a[j].y&1)) a[j].x++;
			int tx=a[j].x,ty=a[j].y;
			a[j].x=(tx+ty)/2;
			a[j].y=(tx-ty)/2;
		}
	}
	return 0;
}