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函数的理解．．．
原来还可以这么写．
有点开心，因为觉得解法有点美．
1/*************************************************************************
2 > File Name: code/cf/#319/E.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年09月18日 星期五 20时55分10秒
6 ************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#include<cctype>
21#define y1 hust111qqz
22#define yn hez111qqz
23#define j1 cute111qqz
24#define ms(a,x) memset(a,x,sizeof(a))
25#define lr dying111qqz
26using namespace std;
27#define For(i, n) for (int i=0;i<int(n);++i)
28typedef long long LL;
29typedef double DB;
30const int inf = 0x3f3f3f3f;
31const int N=1E6+7;
32int n;
33int id[N],x[N],y[N];
34
35bool cmp(int a,int b) //id[a] 和id[b]的大小比较定义
36{
37 if (x[a]<x[b]) return true;
38 if (x[a]>x[b]) return false;
39 if (x[a]%2==1) return y[a]<y[b];
40 else return y[a]>y[b]; //sort的cmp函数原来还可以这么写，长见识了．
41
42}
43int main()
44{
45 #ifndef ONLINE_JUDGE
46 freopen("in.txt","r",stdin);
47 #endif
48 scanf("%d",&n);
49 for ( int i = 0 ; i < n ; i++)
50 {
51 scanf("%d %d",&x[i],&y[i]);
52 x[i] /=1000;
53 y[i] /=1000;
54 id[i] = i;
55 }
56 sort(id,id+n,cmp);
57 for ( int i = 0 ; i < n ; i++)
58 {
59 printf("%d ",id[i]+1);
60 }
61
62
63
64
65 #ifndef ONLINE_JUDGE
66 fclose(stdin);
67 #endif
68 return 0;
69}