奶牛在草地上悠闲的吃着草,因为残象已使它们目不忍视,流言已使它们耳不忍闻。如果两个奶牛的曼哈顿距离(|x,y坐标差|的和)小于等于C,它们处在同一组。问有多少个不同的组。

思路

注意到对于一个点P,曼哈顿距离小于等于c的点组成的集合是一个斜放的正方形,不方便后续操作,我们把它转正。怎么弄呢?对整个坐标系做变换
$$
\begin{bmatrix}
1 & -1 \\
1 & 1
\end{bmatrix} \tag{2}
$$
这是什么意思呢?如果在这个矩阵后面乘一个2行1列的矩阵表示一个(x,y)向量,那么相乘后的结果就是新的(变换后的)(x,y)向量。详情请参考矩阵乘法与向量组相关知识。
原来的$(x,y)$全部变成$(x\times (1,-1) , y\times(1,1) )$也就是$(x-y,x+y)$
这里的矩阵只是为了更规范的描述这个变换。变换其实也可以想成是边把原来的x轴变成了y=x的直线,y轴变成了y=-x的直线,对应的新坐标系中的点在原坐标系中的位置就是变换后的位置。
总之搞这么复杂只是为了达到把正方形搞正的目的。


接着我们考虑什么样的点属于一个组。变换后x,y坐标满足$(x\in[x_0-c,x_0+c],y\in[y_0-c,y_0+c])$的点和(x0,y0)属于一个组。
于是我们可以按y坐标排序,利用扫描线法将当前所有y坐标相差小于等于c的点保存,每添加一个点与适当的点连线,用并查集维护同一个组的元素。


下面考虑如何维护当前的点集,并且高效的连线。
点集可以用multiset<pair<int,int> >维护(不知为何set在洛谷上也可以AC),而连线时注意一下两条:
1.新添加的点与点集中x坐标最小且与x属于同一组的点连线。
2.新添加的点与点集中x坐标最大且与x属于同一组的点连线。
至于为什么这样就可以,而且必须连两条边,请大家琢磨琢磨。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <set>

#define MX 100005
#define oo 999999909

using namespace std;

typedef struct sdf
{
    int x,y;
}point;

point cow[MX];
int n,c;
int fa[MX];
int cnt[MX];
set<pair<int,int> > st;
set<int>ff;

int findfa(int x)
{
    return x==fa[x]?x:fa[x]=findfa(fa[x]);
}

inline bool cmp(point a,point b)
{
    return a.y<b.y;
}

void input()
{
    int x,y;
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        cow[i].x=x-y;
        cow[i].y=x+y;
    }
    sort(cow+1,cow+n+1,cmp);
    for(int i=1;i<=n;i++)fa[i]=i;
}

void work()
{
    int t;
    set<pair<int,int> >::iterator l,r;
    t=1;
    for(int i=1;i<=n;i++)
    {
        while(cow[i].y-cow[t].y>c)st.erase(make_pair(cow[t].x,t)),t++;
        l=st.lower_bound(make_pair(cow[i].x-c,0));
        r=st.lower_bound(make_pair(cow[i].x+c+1,0));
        if((l->first<=cow[i].x+c)&&(l!=st.end()))
            fa[findfa(l->second)]=findfa(i);
        if(r!=st.begin())
            if((--r)->first>=cow[i].x-c)fa[findfa(r->second)]=findfa(i);
        st.insert(make_pair(cow[i].x,i));
    }
    int mxpos=1,tot=0;
    for(int i=1;i<=n;i++)
    {
        cnt[findfa(i)]++;
        if(cnt[findfa(i)]>cnt[mxpos])mxpos=findfa(i);
        if(cnt[findfa(i)]==1)tot++;
    }
    cout<<tot<<" "<<cnt[mxpos]<<endl;
}

int main()
{
    input();
    work();
    return 0;
}
分类: 文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *