给你 n 个点和它们的坐标,现在给它们两两连上边,如果在同一组为黄色,不同组为蓝色。现在让你给出任意一种分组方案,使得所有长度相同的边颜色相同。
2≤n≤103。
发现两点距离相等等价于两点的距离的平方相等,所以考虑距离的平方。
发现要把距离分成两组,不难想到奇偶性分类。设 tpe(x,y)={01x≡y(mod2)x≡y(mod2),由于 (x1,y1),(x2,y2) 的距离的平方 (x1−x2)2+(y1−y2)2 为奇数当且仅当 tpe(x1,y1)=tpe(x2,y2),为偶数当且仅当 tpe(x1,y1)=tpe(x2,y2),那么把 tpe(x,y)=0 的 (x,y) 分到一组,tpe(x,y)=1 的 (x,y) 分到另一组即可。
但是发现 tpe(x,y) 有可能都为 0 或者都为 1,考虑到平移对距离没有影响,所以当 tpe(x,y)=1 时让所有 x 同时加上 1,这样就可以只讨论 tpe(x,y)=0 的情况。
注意到当 tpe(x,y)=0 时 x+y≡x−y≡0(mod2),所以有一个很奇妙的操作:旋转并拉伸坐标系。具体的,让 (x,y)→(2x+y,2x−y) 即让 [xy]→[xy]×[212121−21],由于旋转操作最多进行 logV 次,所以这样可以在 O(nlogV) 的时间复杂度内解决此题。
代码如下:
#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;
}