「BZOJ1604」[Usaco2008 Open] Cow Neighborhoods 奶牛的邻居

2014年9月11日6,7942

Description

了解奶牛们的人都知道,奶牛喜欢成群结队.观察约翰的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均同属一个群.
    给出奶牛们的位置,请计算草原上有多少个牛群,以及最大的牛群里有多少奶牛

Input

   1行输入NC,之后N行每行输入一只奶牛的坐标.

Output

仅一行,先输出牛群数,再输出最大牛群里的牛数,用空格隔开.

Sample Input

4 2
1 1
3 3
2 2
10 10
* Line 1: A single line with a two space-separated integers: the
number of cow neighborhoods and the size of the largest cow
neighborhood.

Sample Output

2 3OUTPUT DETAILS:
There are 2 neighborhoods, one formed by the first three cows and
the other being the last cow. The largest neighborhood therefore
has size 3.

题解

将每个点变为(x+y,x-y)

这样两点的曼哈顿距离就是(|x1 – x2|,|y1 – y2|)

然后将所有点按x坐标排序
用一个队列,维护队列中元素x坐标的差小于c,不满足则左指针右移
对这个队列中元素的y坐标维护平衡树,如果新加入元素的前驱后继与它的y坐标差值不超过c,则用并查集将他们连在一起

 

 

avatar
0 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
提醒