Good Bye 2019E（点坐标缩小一半以区分奇偶性）

设某个点的坐标为（x，y），根据坐标奇偶性公可分为四类，0表示偶数，1表示奇数，（0，0），（0，1），（1，0），（1，1）。

如果所有点的坐标都属于一类，那么它们之间的距离都是4的倍数，无法分辨。

此时将它们的坐标缩小一半，直至区分出奇偶性。

只要有至少一个点的坐标和其他点不在一类里，则可以分为两类。

假设同时存在坐标和为奇数以及坐标和为偶数的点，那么以坐标和为奇数或偶数为标准划分，则两类点在同类中的距离均为4的倍数，而与不同类点的距离是奇数，显然不等，故可行。

如果不能满足上述条件，还可以假设同时存在（0，0）和（1，1）或者同时存在（0，1）和（1，0）的点，那么以横坐标是否为偶数进行划分，则两类点在同类中的距离均为4的倍数，而与不同类点的距离为4的倍数+2（两个奇数相加必定和为2，剩余部分为两个偶数的平方必定为4的倍数），显然距离不等，故可行。

所以关键在于将所有的点都通过缩小的方式把它们分为至少2类。

如果坐标很小的情况下，除以2会将其奇偶性抹去，所以可以先把点的坐标加上初始最大值1e6。

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    vector<pair<int, int>> p(n);
    for (int i = 0; i<n; i++) {cin>>p[i].first>>p[i].second; p[i].first+=1e6; p[i].second+=1e6;}
    while (true){
        vector<vector<int>> cnt(2, vector<int>(2));
        for (int i = 0; i<n; i++) cnt[p[i].first%2][p[i].second%2]++;
        if (cnt[0][0]+cnt[1][1]>0 && cnt[0][1]+cnt[1][0]>0){
            vector<int> A;
            for (int i = 0; i<n; i++) if ((p[i].first + p[i].second)%2==0) A.push_back(i);
            cout<<A.size()<<endl;
            for (auto it: A) cout<<it+1<<' ';
            return 0;
        }
        if (cnt[0][0]+cnt[0][1]>0 && cnt[1][1]+cnt[1][0]>0){
            vector<int> A;
            for (int i = 0; i<n; i++) if (p[i].first%2==0) A.push_back(i);
            cout<<A.size()<<endl;
            for (auto it: A) cout<<it+1<<' ';
            return 0;
        }
        int x, y;
        for (int i = 0; i<2; i++)
            for (int j = 0; j<2; j++) if (cnt[i][j]>0) {x = i; y = j;}
        for (int i = 0; i<n; i++) {p[i].first = (p[i].first - x)/2; p[i].second = (p[i].second - y)/2;}
    }
}

#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
int a[1007],b[1007];
int ans[1007];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i]>>b[i];
    int cnt=0;
    while(cnt==0||cnt==n){
        cnt=0;
        for(int i=1;i<=n;++i){
            if((a[i]+b[i])&1)
                ans[++cnt]=i;
            int x=a[i],y=b[i];
            a[i]=(x+y)>>1;
            b[i]=(x-y)>>1;
        }
    }
    cout<<cnt<<"
";
    for(int i=1;i<=cnt;++i)
        cout<<ans[i]<<" ";
 
    return 0;
}