Codeforces Round #319 (Div. 2) E - Points on Plane

时间:2021-11-06 19:47:20

题目大意:在一个平面里有n个点,点坐标的值在1-1e6之间,让你给出一个遍历所有点的顺序,要求每个点走一次,且

曼哈顿距离之和小于25*1e8。

思路:想了一会就有了思路,我们可以把1e6的x,y坐标都分成2000份,每份500,然后这样整个平面就被分成

了2000*2000个区域,然后按区域输出点就行了。

 #include<bits/stdc++.h>
using namespace std;
int n;
vector<int> ans[][];
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
int x,y; scanf("%d%d",&x,&y);
ans[x/][y/].push_back(i);
}
bool flag=false;
for(int i=;i<=;i++)
{
if(!flag)
{
for(int j=;j<=;j++)
{
for(int k:ans[i][j]) printf("%d ",k);
}
}
else
{
for(int j=;j>=;j--)
{
for(int k:ans[i][j]) printf("%d ",k);
}
}
flag=!flag;
}
return ;
}