bzoj 1604: [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居 (曼哈顿距离的转化【拆点】+set+并查集)
http://www.lydsy.com/JudgeOnline/problem.php?id=1604 题意：了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的N(1≤N≤100000)只奶牛，你会发现她们已经结成了几个“群”．每只奶牛在吃草的时候有一个独一无二的位置坐标Xi，Yi(l≤Xi，Yi≤[1．.10^9]；Xi，Yi∈整数．当满足下列两个条件之一，两只奶牛i和j是属于同一个群的： 1．两只奶牛的曼哈顿距离不超过C(1≤C≤10^9)，即lXi - xil+IYi - Yil≤C. 2．两只奶牛有共同的邻居．即，存在一只奶牛k，使i与k，j与k均同属一个群． 给出奶牛们的位置，请计算草原上有多少个牛群，以及最大的牛群里有多少奶牛
思路：一开始并没有什么思路…入手点是关于曼哈顿距离的转化。
> >先看曼哈顿距离的定义
|x1−x2|+|y1−y2|
拆绝对值
x1−x2+y1−y2或x1−x2+y2−y1
x2−x1+y1−y2或x2−x1+y2−y1
即|x1+y1−(x2+y2)|或|x1−y1−(x2−y2)|
设x1+y1为x′，x1−y1为y′
则|x1′−x2′|或|y1′−y2′|
所以原要求1转化为
max(|x1′−x2′|,|y1′−y2′|)<=c
引用自：http://blog.csdn.net/wzq_QwQ/article/details/47746091
这样就有思路了。如果两个点属于同一个群，那么必须这两个点的x的差在c范围内，并且两个点的y的差也在范围内。 我们可以先按照一个 坐标排序，不妨以x为关键字排序，然后维护一段点的序列，使得这段序列中的所有的点的横坐标（其实就是最大减去最小）的差都在c范围内。然后对于序列中的所有点，我们想要知道有没有群“接纳”最新加入的点，二分找到比当前新加入点的纵坐标大的最小值和比当前新加入点的纵坐标小的最大值（set的lower_bound 第一次用），判断是否满足纵坐标的差在c的范围内。如果是，则用并差集合合并一下。
用multiset的原因是经过变换后点的坐标可能重复，以及multiset删除元素的时候不能直接删，因为会把所有相同的值删掉。
重要的话再说一遍：这道题最关键也是最大的收货就是，关于曼哈顿距离的变换。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年02月24日 星期三 13时36分09秒
4File Name :code/bzoj/1604.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const LL linf =1E17;
34const int N=1E5+7;
35int n;
36int father[N];
37struct point
38{
39 LL x,y;
40 int id; //合并的时候需要用到原来的序号
41 point (){}
42 point (LL _x,LL _y,int _id):x(_x),y(_y),id(_id){};
43
44 bool operator<(point b)const
45 {
46 return y<b.y;
47 }
48}p[N];
49LL c;
50
51multiset<point>se; //因为变换坐标后可能有相同的蒂娜所以要用multiset...?
52multiset<point>::iterator it,it2;
53
54queue<point>q;
55
56
57int cnt[N];
58int total;
59bool cmp(point a,point b)
60{
61 return a.x<b.x;
62}
63void init()
64{
65 ms(cnt,0);
66 ms(father,0);
67 for ( int i = 1 ; i <N ; i++) father[i] = i;
68
69 total = n ;
70}
71
72int root( int x)
73{
74 if (x==father[x]) return x;
75 else return father[x]=root(father[x]);
76}
77
78void merge(int x,int y)
79{
80 int rx=root(x);
81 int ry=root(y);
82 if (rx!=ry) father[rx]=ry,total--;
83}
84
85LL labs(LL x)
86{
87 if (x>0) return x;
88 else return -x;
89}
90int main()
91{
92 #ifndef ONLINE_JUDGE
93 freopen("code/in.txt","r",stdin);
94 #endif
95
96 ios::sync_with_stdio(false);
97
98 cin>>n>>c;
99 init();
100 for ( int i = 1 ; i <= n ; i++)
101 {
102 LL x,y;
103 cin>>x>>y;
104 p[i]=point(x+y,x-y,i);
105 }
106
107 sort(p+1,p+n+1,cmp);
108
109 se.insert((point){0,linf,0});
110 se.insert((point){0,-linf,0});
111 se.insert(p[1]);
112 int head = 1;
113
114 for ( int i = 2 ; i <= n ; i++)
115 {
116 while (p[i].x-p[head].x>c)
117 {
118 se.erase(se.find(p[head])); //注意multiset删除元素的时候的写法...写erase(p[head])的话会把所有相同的都删了
119 head++;
120// cout<<"head:"<<head<<endl;
121 }
122// cout<<"sad"<<endl;
123
124
125 it = se.lower_bound(p[i]);
126 it2 = it;
127 it2--;
128 if (labs(it->y-p[i].y)<=c) merge(it->id,p[i].id);
129 if (labs(it2->y-p[i].y)<=c) merge(it2->id,p[i].id);
130
131 se.insert(p[i]);
132 }
133
134
135 for ( int i = 1 ;i <= n ; i++)
136 cnt[root(i)]++;
137
138 int mx = -1;
139 for ( int i = 1 ; i <= n ; i++)
140 mx = max(mx,cnt[i]);
141
142 cout<<total<<" "<<mx<<endl;
143
144
145
146
147
148 #ifndef ONLINE_JUDGE
149 fclose(stdin);
150 #endif
151 return 0;
152}