codeforces #319 div 2 E C. Points on Plane (分块)
初识分快.
引一段题解：
Let's split rectangle 106 × 106 by vertical lines into 1000 rectangles 103 × 106. Let's number them from left to right. We're going to pass through points rectangle by rectangle. Inside the rectangle we're going to pass the points in increasing order of y-coordinate if the number of rectangle is even and in decreasing if it's odd.
Let's calculate the maximum length of such a way. The coordinates are independent. By y-coordinate we're passing 1000 rectangles from0 to 106, 109 in total. By x-coordinate we're spending 1000 to get to the next point of current rectangle and 2000 to get to next rectangle. That means, 2 * 109 + 2000000 in total, which perfectly fits.
The complexity is O(n * log(n))
并不会做，看了题解写的，感觉好神奇...
然后加深了sort的cmp函数的理解．．．
原来还可以这么写．
有点开心，因为觉得解法有点美．
/*************************************************************************
> File Name: code/cf/#319/E.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年09月18日 星期五 20时55分10秒
************************************************************************/
1#include<iostream>
2#include<iomanip>
3#include<cstdio>
4#include<algorithm>
5#include<cmath>
6#include<cstring>
7#include<string>
8#include<map>
9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#include<cctype>
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define ms(a,x) memset(a,x,sizeof(a))
18#define lr dying111qqz
19using namespace std;
20#define For(i, n) for (int i=0;i<int(n);++i)
21typedef long long LL;
22typedef double DB;
23const int inf = 0x3f3f3f3f;
24const int N=1E6+7;
25int n;
26int id[N],x[N],y[N];
1bool cmp(int a,int b) //id[a] 和id[b]的大小比较定义
2{
3 if (x[a]<x[b]) return true;
4 if (x[a]>x[b]) return false;
5 if (x[a]%2==1) return y[a]<y[b];
6 else return y[a]>y[b]; //sort的cmp函数原来还可以这么写，长见识了．
1}
2int main()
3{
4 #ifndef ONLINE_JUDGE
5 freopen("in.txt","r",stdin);
6 #endif
7 scanf("%d",&n);
8 for ( int i = 0 ; i < n ; i++)
9 {
10 scanf("%d %d",&x[i],&y[i]);
11 x[i] /=1000;
12 y[i] /=1000;
13 id[i] = i;
14 }
15 sort(id,id+n,cmp);
16 for ( int i = 0 ; i < n ; i++)
17 {
18 printf("%d ",id[i]+1);
19 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}