POJ 3241 Object Clustering 莫队算法

第n-k大曼哈顿距离,莫队算法裸题

Object Clustering Time Limit: 2000MS   Memory Limit: 131072K Total Submissions: 1584   Accepted: 366 Description We have N (N ≤ 10000) objects, and wish to classify them into several groups by judgement of their resemblance. To simply the model, each object has 2 indexes a and b (a, b ≤ 500). The resemblance of object i and object j is defined by dij = |ai – aj| + |bi – bj|, and then we say i is dij resemble to j. Now we want to find the minimum value of X, so that we can classify the N objects into K (K < N) groups, and in each group, one object is at most X resemble to another object in the same group, i.e, for every object i, if i is not the only member of the group, then there exists one object j (i ≠ j) in the same group that satisfies dij ≤ X Input The first line contains two integers N and K. The following N lines each contain two integers a and b, which describe a object. Output A single line contains the minimum X. Sample Input 6 2 1 2 2 3 2 2 3 4 4 3 3 1 Sample Output 2 Source POJ Monthly–2007.08.05, Li, Haoyuan

[Submit]   [Go Back]   [Status]   [Discuss]

/* *********************************************** Author        :CKboss Created Time  :2014年12月20日 星期六 00时27分00秒 File Name     :POJ3241.cpp ************************************************ */  #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <cmath> #include <cstdlib> #include <vector> #include <queue> #include <set> #include <map>  using namespace std;  const int maxn=22000; const int INF=0x3f3f3f3f;  int n,k;  struct Edge {  int u,v,w; }edge[maxn<<2]; int tot;  bool cmp_E(Edge a,Edge b) {  return a.w<b.w; }  struct Point {  int x,y,id; }pt[maxn];  bool cmp_P(Point a,Point b) {  if(a.x!=b.x) return a.x<b.x;  return a.y<b.y; }  int lowbit(int x) { return x&(-x); }  int C[4000],D[4000];  void update(int id,int pos,int val) {  pos+=1000;  for(int i=pos;i;i-=lowbit(i))  {   if(C[i]>val)   {    C[i]=val; D[i]=id;   }  } }  void query(int id,int pos,int val) {  pos+=1000;  int Fr=-1,ret=INF;  for(int i=pos;i<4000;i+=lowbit(i))  {   if(ret>C[i])   {    ret=C[i]; Fr=D[i];   }  }  if(Fr!=-1) edge[tot++]=(Edge){id,Fr,ret-val}; }  void gao() {  memset(C,63,sizeof(C));  sort(pt,pt+n,cmp_P);  for(int i=n-1;i>=0;i--)  {   int pos=pt[i].y-pt[i].x;   int sum=pt[i].y+pt[i].x;   int id=pt[i].id;   query(id,pos,sum);   update(id,pos,sum);  } }  int fa[maxn];  int find(int x) {  if(x==fa[x]) return x;  return fa[x]=find(fa[x]); }  bool merge(int a,int b) {  a=find(a); b=find(b);  if(a==b) return false;  fa[a]=b;  return true; }  int solve() {  if(n==k) return 0;   tot=0;   gao();   for(int i=0;i<n;i++)   swap(pt[i].x,pt[i].y);  gao();   for(int i=0;i<n;i++)   pt[i].y=-pt[i].y;  gao();   for(int i=0;i<n;i++)   swap(pt[i].x,pt[i].y);  gao();   for(int i=0;i<n;i++) fa[i]=i;  sort(edge,edge+tot,cmp_E);  for(int i=0;i<tot;i++)  {   if(merge(edge[i].u,edge[i].v)==true)   {    n--; if(n==k) return edge[i].w;   }  }   return -1; }  int main() {     //freopen("in.txt","r",stdin);     //freopen("out.txt","w",stdout);       while(scanf("%d%d",&n,&k)!=EOF)  {   for(int i=0;i<n;i++)   {    int x,y;    scanf("%d%d",&x,&y);    pt[i].x=x; pt[i].y=y; pt[i].id=i;   }   printf("%d/n",solve());  }       return 0; }