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删除元素的时候不能直接删，因为会把所有相同的值删掉。
重要的话再说一遍：这道题最关键也是最大的收货就是，关于曼哈顿距离的变换。
/* ***********************************************
Author :111qqz
Created Time :2016年02月24日 星期三 13时36分09秒
File Name :code/bzoj/1604.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const LL linf =1E17;
7const int N=1E5+7;
8int n;
9int father[N];
10struct point
11{
12 LL x,y;
13 int id; //合并的时候需要用到原来的序号
14 point (){}
15 point (LL _x,LL _y,int _id):x(_x),y(_y),id(_id){};
1 bool operator<(point b)const
2 {
3 return y<b.y;
4 }
5}p[N];
6LL c;
multiset<point>se; //因为变换坐标后可能有相同的蒂娜所以要用multiset...?
multiset<point>::iterator it,it2;
queue<point>q;
1int cnt[N];
2int total;
3bool cmp(point a,point b)
4{
5 return a.x<b.x;
6}
7void init()
8{
9 ms(cnt,0);
10 ms(father,0);
11 for ( int i = 1 ; i <N ; i++) father[i] = i;
total = n ;
}
1int root( int x)
2{
3 if (x==father[x]) return x;
4 else return father[x]=root(father[x]);
5}
1void merge(int x,int y)
2{
3 int rx=root(x);
4 int ry=root(y);
5 if (rx!=ry) father[rx]=ry,total--;
6}
1LL labs(LL x)
2{
3 if (x>0) return x;
4 else return -x;
5}
6int main()
7{
8 #ifndef ONLINE_JUDGE
9 freopen("code/in.txt","r",stdin);
10 #endif
ios::sync_with_stdio(false);
1 cin>>n>>c;
2 init();
3 for ( int i = 1 ; i <= n ; i++)
4 {
5 LL x,y;
6 cin>>x>>y;
7 p[i]=point(x+y,x-y,i);
8 }
sort(p+1,p+n+1,cmp);
1 se.insert((point){0,linf,0});
2 se.insert((point){0,-linf,0});
3 se.insert(p[1]);
4 int head = 1;
1 for ( int i = 2 ; i <= n ; i++)
2 {
3 while (p[i].x-p[head].x>c)
4 {
5 se.erase(se.find(p[head])); //注意multiset删除元素的时候的写法...写erase(p[head])的话会把所有相同的都删了
6 head++;
7// cout<<"head:"<<head<<endl;
8 }
9// cout<<"sad"<<endl;
1 it = se.lower_bound(p[i]);
2 it2 = it;
3 it2--;
4 if (labs(it->y-p[i].y)<=c) merge(it->id,p[i].id);
5 if (labs(it2->y-p[i].y)<=c) merge(it2->id,p[i].id);
se.insert(p[i]);
}
for ( int i = 1 ;i <= n ; i++)
cnt[root(i)]++;
1 int mx = -1;
2 for ( int i = 1 ; i <= n ; i++)
3 mx = max(mx,cnt[i]);
cout<<total<<" "<<mx<<endl;
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}