CF1270E Divide Points

神仙题，需要一些几何和代数的直觉

题意：

给出$n$个直角坐标系上的点，两两连边，现要求将它们分成两个非空点集，使得同点集连边的长度不会在异点集连边的长度中有相同的出现

题解：

首先要意识到这么一种划分方式：设点坐标$(x,y)$，特征值$p=x+y$，将$p$的奇偶性相同的点划分在一起

为什么这样是正确的呢？因为$p$奇偶性相同的点之间的连边一定是偶数的（指不开根号），否则一定是奇数的，这一点有疑问的话可以用代数简单的证明得到

问题看起来就这样解决了，但题目还有一个要求：点集非空

这样当所有的$p$都是奇数或都是偶数时就不合法了

怎么办呢？下面开始神仙操作了：

考虑将原图形等比例缩小一半（指面积），此时不变的是边之间的大小关系，改变的是每个点的$p$值的奇偶性，这保证了继续使用上述划分方法的正确性

那如何让图形缩小一半呢？这就要用到切比雪夫距离了

具体的，若原来的点$A$坐标$(x,y)$，那它变换后的对应点$A’$就是$(\frac{x+y}{2},\frac{x-y}{2})$

形象的，可以看下下面这张图：

（其实不仅缩小了，还旋转了45度呢）

为啥这么神奇呢？我也不知道哈qwq

这样就可以对图形一直做这种变换，直到有个点的$p$的奇偶性不同于其它的点为止

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=1e3+5;
int a[N],n,x[N],y[N];
vector<int> odd;

signed main(){
    read(n);
    for(int i=1;i<=n;i++){
        read(x[i]);read(y[i]);
        a[i]=x[i]+y[i];
        if(a[i]&1) odd.push_back(i);
    }
    while(odd.empty()||odd.size()==n){
        odd.clear();
        for(int i=1;i<=n;i++){
            int xx=x[i],yy=y[i];
            x[i]=xx+yy>>1;
            y[i]=xx-yy>>1;
            a[i]=x[i]+y[i];
            if(a[i]&1) odd.push_back(i);
        }
    }
    write(odd.size());puts("");
    for(int i=0;i<odd.size();i++) write(odd[i]),putchar(' ');
}