CodeForecs 1270E Divide Points
https://codeforces.com/contest/1270/problem/E
平面上有 \(n\) 个两两不同的点,其中第 \(i\) 个点坐标为 \((x_i,y_i)\) .
现在需要将其分为两个非空集合 \(A,B\) ,满足每个点要么在 \(A\) 内,要么在 \(B\) 内.
枚举每一对点,若它们在同一集合内,则用蓝色写下它们之间的欧几里得距离,若它们在不同集合,则将黄色写下它们之间的欧几里得距离.若存在黄色和蓝色的数字相同,则这个方案非法.
求一个合法方案,可以证明,总是存在这样的方案.
Tutorial
考虑按 \(x,y\) 坐标的奇偶性将所有点分为 \(A_{00},A_{11},A_{01},A_{10}\) 这 \(4\) 个集合.
若只有所有点都在同一个集合.例如 \(A_{00}\) ,则将它们的坐标全部除以 \(2\) ,由于这相当于平移和缩放,所以问题的方案仍然适用.
假如坐标和为偶数的集合 \(A_{00} \cup A_{11}\) ,坐标和为奇数的集合 \(A_{01} \cup A_{10}\) 的集合都不为空,则令 \(A=A_{00} \cup A_{11}\) , \(B= A_{01} \cup A_{10}\) ,这样的话,距离的平方 \((x_i-x_j)^2+(y_i-y_j)^2\) 满足若是同一集合中的点则为偶数,若是不同集合中的点则为奇数.
否则,若 \(A_{00},A_{11}\) 不为空,则令 \(A=A_{00},B=A_{11}\) ,这样距离的平方 \((x_i-x_j)^2+(y_i-y_j)^2\) 满足若是同一集合中的点则被 \(4\) 整除,若是不同集合的点则除 \(4\) 余数为 \(2\)
若 \(A_{01},A_{10}\) 不为空与上一种情况类似.
复杂度为 \(O(n \log X)\) ,其中 \(X\) 表示距离的最大值.
Code
#include <cassert>
#include <cstdio>
#include <iostream>
#include <vector>
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
inline char nc()
{
return getchar();
static char buf[100000],*l=buf,*r=buf;
return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<class T> void read(T &x)
{
x=0; int f=1,ch=nc();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=nc();}
x*=f;
}
const int maxn=1000+5;
int n;
int x[maxn];
int y[maxn];
vector<int> A[2][2];
int main()
{
read(n);
for(int i=1;i<=n;++i)
{
read(x[i]),read(y[i]);
}
while(true)
{
for(int i=0;i<2;++i) for(int j=0;j<2;++j)
{
A[i][j].clear();
}
for(int i=1;i<=n;++i)
{
int a=bool(x[i]%2),b=bool(y[i]%2);
A[a][b].push_back(i);
}
int a=-1,b=-1;
for(int i=0;i<2;++i)
{
for(int j=0;j<2;++j) if(A[i][j].size())
{
if(a==-1) a=i,b=j;
else a=-2;
}
}
if(a>=0)
{
for(int i=0;i<A[a][b].size();++i)
{
int u=A[a][b][i];
x[u]=(x[u]-a)/2;
y[u]=(y[u]-b)/2;
}
continue;
}
if(A[0][0].size()+A[1][1].size()&&A[0][1].size()+A[1][0].size())
{
printf("%d\n",int(A[0][0].size()+A[1][1].size()));
bool flag=0;
for(int i=0;i<A[0][0].size();++i)
{
if(flag) printf(" "); else flag=1;
printf("%d",A[0][0][i]);
}
for(int i=0;i<A[1][1].size();++i)
{
if(flag) printf(" "); else flag=1;
printf("%d",A[1][1][i]);
}
printf("\n");
break;
}
if(A[0][0].size()+A[1][1].size())
{
printf("%d\n",int(A[0][0].size()));
for(int i=0;i<A[0][0].size();++i)
{
if(i) printf(" ");
printf("%d",A[0][0][i]);
}
printf("\n");
break;
}
if(A[0][1].size()+A[1][0].size())
{
printf("%d\n",int(A[0][1].size()));
for(int i=0;i<A[0][1].size();++i)
{
if(i) printf(" ");
printf("%d",A[0][1][i]);
}
printf("\n");
break;
}
}
return 0;
}