Poj3241 Object Clustering

Position：

http://poj.org/problem?id=3241

---

List

Poj3241 Object Clustering ListDescriptionKnowledgeSolutionNoticeCode感谢

Description

大意：求曼哈顿距离最小生成树上第k大（第n-k小）的边。

Knowledge

参考曼哈顿距离最小生成树 http://blog.csdn.net/yjpyjp2014/article/details/52180707

Solution

分析： 1.由上面资料可知，每45度的范围只算一个最近点 2.看下面一种情况： 　　　　　　 对于下面那个点，上面的点在它的右上方。而它又在上面的点的左下方，故我们只需计算左上和右上，即角[0,180]的范围，每45度一个，每个点4个，故边数不超过4×n。 3-1.为了写代码的方便，我们每次将点翻转，只计算[45,90]范围的点。翻转：①第一次不翻②第二次将一个点的x与y交换(即沿y=x翻转，原本在[0,45]的点翻到了[45,90])③将x=-x，沿x=0翻转，左上翻到右上④ 3-2.ZYT的写法(可能容易理解一点):我们只需考虑在一块区域内的点，其他区域内的点可以通过坐标变换“移动”到这个区域内。为了方便处理，我们考虑在y轴向右45度的区域。在某个点A(x0,y0)的这个区域内的点B(x1,y1)满足x1≥x0且y1-x1>y0-x0。这里对于边界我们只取一边，但是操作中两边都取也无所谓。那么|AB|=y1-y0+x1-x0=(x1+y1)-(x0+y0)。在A的区域内距离A最近的点也即满足条件的点中x+y最小的点。因此我们可以将所有点按x坐标排序，再按y-x离散，用线段树或者树状数组维护大于当前点的y-x的最小的x+y对应的点（也就是维护区间最小值）。时间复杂度O(NlogN)。至于坐标变换，一个比较好处理的方法是第一次直接做(R1==R5)；第二次沿直线y=x翻转，即交换x和y坐标(R2==R6)；第三次沿直线x=0翻转，即将x坐标取相反数(R7==R3)；第四次再沿直线y=x翻转(R8==R4)。注意只需要做4次，因为边是双向的。 　　　　　　　　　　　　　 4.对于点(x,y)如果有一个点(x1,y1)在它的(45,90)，只要满足y1-x1>y-x(证明：即用一条斜率为45的直线，过这个点，比截距的大小y=x+b，y-x=b，平面图知识qaq~) 5.按x坐标排序，从后往前扫，值域(y-x)树状数组，w记录的是曼哈顿距离，pos记录第几个点。

Notice

1.这是一个反的树状数组，c[i]记录i~i+lowbit(i)-1 2.因为只要求x~m的最小值，用树状数组可以

Code

// <ObjectClustering.cpp> - 08/11/16 16:35:38 // This file is made by YJinpeng，created by XuYike's black technology automatically. // Copyright (C) 2016 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cstdlib> #include <cmath> #define MOD 1000000007 #define INF 1e9 #define EPS 1e-10 using namespace std; typedef long long LL; const int MAXN=10010; const int MAXM=100010; inline int max(int &x,int &y) {return x>y?x:y;} inline int min(int &x,int &y) {return x<y?x:y;} inline int getint() { register int w=0,q=0;register char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')q=1,ch=getchar(); while(ch>='0'&&ch<='9')w=w*10+ch-'0',ch=getchar(); return q?-w:w; } int n,m,k,tot,cnt,x,pos; int f[MAXN],hs[MAXN],t[MAXN]; struct Point{ int x,y,id; void read(){x=getint();y=getint();} friend bool operator < (const Point &a,const Point &b) { return a.x==b.x?a.y<b.y:a.x<b.x; } }p[MAXN]; struct Edge{ int u,v,w; friend bool operator < (const Edge &a,const Edge &b){ return a.w<b.w; } }e[MAXN*4]; struct Bit{ int w,pos; void Pre(){pos=-1,w=INF;} }b[MAXN]; inline int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);} inline int Lowbit(int x){return x&(-x);} int Dis(int a,int b){ return abs(p[a].x-p[b].x)+abs(p[a].y-p[b].y); } int Query(int x){ int M=INF,pos=-1; for(int i=x;i<=m;i+=Lowbit(i)) if(b[i].w<M)M=b[i].w,pos=b[i].pos; return pos; } void Update(int x,int M,int pos){ for(int i=x;i;i-=Lowbit(i)) if(M<b[i].w)b[i].w=M,b[i].pos=pos; } void Insert(int u,int v,int w){ e[++cnt].u=u;e[cnt].v=v;e[cnt].w=w; } void Caledge(){ sort(p+1,p+1+n); for(int i=1;i<=n;i++)hs[i]=t[i]=p[i].y-p[i].x; sort(hs+1,hs+1+n); m=unique(hs+1,hs+1+n)-hs; for(int i=1;i<=m;i++)b[i].Pre(); for(int i=n;i>=1;i--){ x=lower_bound(hs+1,hs+1+m,t[i])-hs+1; pos=Query(x); if(pos!=-1)Insert(p[i].id,p[pos].id,Dis(i,pos)); Update(x,p[i].x+p[i].y,i); } } void Kruskal(){ sort(e+1,e+1+cnt);tot=0; for(int i=1;i<=n;i++)f[i]=i; for(int i=1;i<=cnt;i++){ f[e[i].u]=Find(f[e[i].u]); f[e[i].v]=Find(f[e[i].v]); if(f[e[i].u]!=f[e[i].v])f[f[e[i].u]]=f[e[i].v],tot++; if(tot==k){printf("%d",e[i].w);break;} } } int main() { freopen("ObjectClustering.in","r",stdin); freopen("ObjectClustering.out","w",stdout); n=getint();k=n-getint(); for(int i=1;i<=n;i++)p[i].read(),p[i].id=i; for(int j=1;j<=4;j++){ if(j==2||j==4) for(int i=1;i<=n;i++)swap(p[i].x,p[i].y); else if(j==3) for(int i=1;i<=n;i++)p[i].x=-p[i].x; Caledge(); } Kruskal(); return 0; }

感谢

Friend ZYT的大力支持