首页 > ACM题库 > HDU-杭电 > HDU 2966-In case of failure[解题报告]HOJ
2014
02-24

HDU 2966-In case of failure[解题报告]HOJ

In case of failure

问题描述 :

To help their clients deal with faulty Cash Machines, the board of The Planar Bank has decided to stick a label expressing sincere regret and sorrow of the bank about the failure on every ATM. The very same label would gently ask the customer to calmly head to the nearest Machine (that should hopefully
work fine).

In order to do so, a list of two-dimensional locations of all n ATMs has been prepared, and your task is to find for each of them the one closest with respect to the Euclidean distance.

输入:

The input contains several test cases. The very first line contains the number of cases t (t <= 15) that follow. Each test cases begin with the number of Cash Machines n (2 <= n <= 10^5). Each of the next n lines contain the coordinates of one Cash Machine x,y (0 <= x,y <=10^9) separated by a space. No two
points in one test case will coincide.

输出:

The input contains several test cases. The very first line contains the number of cases t (t <= 15) that follow. Each test cases begin with the number of Cash Machines n (2 <= n <= 10^5). Each of the next n lines contain the coordinates of one Cash Machine x,y (0 <= x,y <=10^9) separated by a space. No two
points in one test case will coincide.

样例输入:

2
10
17 41
0 34
24 19
8 28
14 12
45 5
27 31
41 11
42 45
36 27
15
0 0
1 2
2 3
3 2
4 0
8 4
7 4
6 3
6 1
8 0
11 0
12 2
13 1
14 2
15 0

样例输出:

200
100
149
100
149
52
97
52
360
97
5
2
2
2
5
1
1
2
4
5
5
2
2
2
5


#include <iostream>
 #include<cstdio>
 #include<cstring>
 #include<cmath>
 #include<algorithm>
 using namespace std;
 #define D 2
 #define N 200010
 const int inf=1000000001;
 const long long Inf=1ll*inf*inf;
 struct kdnode
 {
     int x[D];
     int split;
     int l,r,p;
 } kdtree[N],q[N];
 bool operator==(const kdnode &a,const kdnode &b)
 {
     for(int i=0; i<D; i++)
     {
         if(a.x[i]!=b.x[i])return false;
     }
     return true;
 }
 double avg[D],var[D];
 int n;
 void calAvg(int l,int r)
 {
     for(int i=0; i<D; i++)avg[i]=0;
     for(int i=l; i<=r; i++)
         for(int j=0; j<D; j++)
             avg[j]+=1.0*kdtree[i].x[j]/(r-l+1);
 }
 void calVar(int l,int r)
 {
     for(int i=0; i<D; i++)var[i]=0;
     for(int i=l; i<=r; i++)
         for(int j=0; j<D; j++)
             var[j]+=1.0*(kdtree[i].x[j]-avg[j])/n*(kdtree[i].x[j]-avg[j]);
 }
 int splitD;
 double maxVar;
 bool cmp(kdnode a,kdnode b)
 {
     return a.x[splitD]<b.x[splitD];
 }
 int construct(int p,int l,int r)
 {
     if(r<l)return -1;
     int root=(l+r)/2;
     calAvg(l,r);
     calVar(l,r);
     maxVar=-1.0;
     for(int i=0; i<D; i++)
         if(var[i]>maxVar)
             maxVar=var[i],splitD=i;
     sort(kdtree+l,kdtree+r+1,cmp);
     kdtree[root].split=splitD;
     kdtree[root].l=construct(root,l,root-1);
     kdtree[root].r=construct(root,root+1,r);
     kdtree[root].p=p;
     return root;
 }
 int Find(int root,kdnode x)
 {
     if(root==-1)return -1;
     if(x==kdtree[root])
     {
         return root;
     }
     int d=kdtree[root].split;
     if(x.x[d]>kdtree[root].x[d])
     {
         return Find(kdtree[root].r,x);
     }
     else if(x.x[d]<kdtree[root].x[d])
     {
         return Find(kdtree[root].l,x);
     }
     else
     {
         int l=Find(kdtree[root].l,x);
         int r=Find(kdtree[root].r,x);
         return (l==-1?r:l);
     }
 }
 int FindMin(int root,int d)
 {
     int ret=root;
     if(kdtree[root].l!=-1)
     {
         int v=FindMin(kdtree[root].l,d);
         if(kdtree[ret].x[d]>kdtree[v].x[d])
             ret=v;
     }
     if(kdtree[root].r!=-1)
     {
         int v=FindMin(kdtree[root].r,d);
         if(kdtree[ret].x[d]>kdtree[v].x[d])
             ret=v;
     }
     return ret;
 }
 int FindMax(int root,int d)
 {
     int ret=root;
     if(kdtree[root].l!=-1)
     {
         int v=FindMax(kdtree[root].l,d);
         if(kdtree[ret].x[d]<kdtree[v].x[d])
             ret=v;
     }
     if(kdtree[root].r!=-1)
     {
         int v=FindMax(kdtree[root].r,d);
         if(kdtree[ret].x[d]<kdtree[v].x[d])
             ret=v;
     }
     return ret;
 }
 void DeleteNode(int v)
 {
     int p=kdtree[v].p;
     kdtree[v].p=-1;
     if(kdtree[p].l==v)
         kdtree[p].l=-1;
     else
         kdtree[p].r=-1;
 }
 void Remove(int root,kdnode x)
 {
     int pos=Find(root,x);
     if(kdtree[pos].l==-1&&kdtree[pos].r==-1)
     {
         DeleteNode(pos);
     }
     else if(kdtree[pos].l==-1)
     {
         int alt=FindMin(kdtree[pos].r,kdtree[pos].split);
         for(int i=0; i<D; i++)kdtree[pos].x[i]=kdtree[alt].x[i];
         Remove(alt,kdtree[alt]);
     }
     else
     {
         int alt=FindMax(kdtree[pos].l,kdtree[pos].split);
         for(int i=0; i<D; i++)kdtree[pos].x[i]=kdtree[alt].x[i];
         Remove(alt,kdtree[alt]);
     }
 }
 void Insert(int root,int x)
 {
     int d=kdtree[root].split;
     if(kdtree[root].x[d]<kdtree[x].x[d])
     {
         if(kdtree[root].r==-1)
         {
             kdtree[root].r=x;
             kdtree[x].p=root;
         }
         else Insert(kdtree[root].r,x);
     }
     else
     {
         if(kdtree[root].l==-1)
         {
             kdtree[root].l=x;
             kdtree[x].p=root;
         }
         else Insert(kdtree[root].l,x);
     }
 }
 void Add(int root,kdnode x)
 {
     int pos=n;
     kdtree[n++]=x;
     Insert(root,pos);
 }
 
 long long dist(kdnode a,kdnode b)
 {
     long long ret=0;
     for(int i=0; i<D; i++)
     {
         ret+=1ll*(a.x[i]-b.x[i])*(a.x[i]-b.x[i]);
     }
     return ret;
 }
 long long query(int root,kdnode x)
 {
     if(root==-1)return Inf;
     int d=kdtree[root].split;
     long long ret;
     if(x.x[d]<kdtree[root].x[d])
     {
         ret=query(kdtree[root].l,x);
         double dd=1.0*x.x[d]+sqrt(1.0*ret);
         if(dd>=1.0*kdtree[root].x[d])
         {
             ret=min(ret,query(kdtree[root].r,x));
         }
     }
     else if(x.x[d]>kdtree[root].x[d])
     {
         ret=query(kdtree[root].r,x);
         double dd=1.0*x.x[d]-sqrt(1.0*ret);
         if(dd<=1.0*kdtree[root].x[d])
         {
             ret=min(ret,query(kdtree[root].l,x));
         }
     }
     else
     {
         ret=query(kdtree[root].l,x);
         ret=min(ret,query(kdtree[root].r,x));
     }
     ret=min(ret,dist(kdtree[root],x));
     return ret;
 }
 int main()
 {
 //    freopen("in","r",stdin);
     int t;
     scanf("%d",&t);
     while(t--)
     {
         scanf("%d",&n);
         for(int i=0; i<n; i++)
         {
             kdtree[i].split=0;
             kdtree[i].p=kdtree[i].l=kdtree[i].r=-1;
             for(int j=0; j<D; j++)
             {
                 scanf("%d",&kdtree[i].x[j]);
                 q[i]=kdtree[i];
             }
         }
 
         int root=construct(-1,0,n-1);
 
         int m=n;
         for(int i=0; i<m; i++)
         {
             Remove(root,q[i]);
             cout<<query(root,q[i])<<endl;
             Add(root,q[i]);
         }
     }
     return 0;
 }

 


解题参考:http://www.cnblogs.com/nyroro/articles/2512680.html