CF1270E Divide Points 做题记录

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

2n1032 \le n \le 10^3

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

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

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

注意到当 tpe(x,y)=0\operatorname{tpe}(x,y)=0x+yxy0(mod2)x+y\equiv x-y\equiv 0\pmod2,所以有一个很奇妙的操作:旋转并拉伸坐标系。具体的,让 (x,y)(x+y2,xy2)(x,y)\to(\frac{x+y}{2},\frac{x-y}{2}) 即让 [xy][xy]×[12121212]\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},由于旋转操作最多进行 logV\log V 次,所以这样可以在 O(nlogV)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;
}