題意:
給定1個網格圖，其上有1堆壞點(整點，同1位置多個)，求1個整點，使得該整點到所有的壞點的切比雪夫距離之和最小。
求這個整點位置。
無SPJ
解析:
看完題懵了，我只會曼哈頓距離啊怎樣辦。
然后就無聊查了下給定的那個計算公式，哇塞這竟然叫切比雪夫距離。
噫怎樣有個鏈接是談切比雪夫轉化曼哈頓距離的。
噫看完后我就會這道題辣！
對原坐標系中兩點間的 Chebyshev 距離，是將坐標軸順(逆)時針旋轉45度并將所有點的坐標值放大sqrt(2)倍所得到的新坐標系中的Manhattan距離的2分之1。
某點繞原點逆時針旋轉α°（或坐標軸順時針旋轉）后，點(x,y)的坐標會變成(cosα*x - sinα*y , sinα*x + cosα*y)。
有了以上兩個東西這題就解辣
明顯點(x,y)逆時針旋轉45度坐標值放大sqrt(2)倍后的坐標是(x-y,x+y)。
因而我們直接把所有點弄過去，分別求x,y的中位數便可。
然后轉回來的點有兩種:第1坐標都是整數那末直接輸出便可。
第2坐標有不是整數的(即.5)我們需要判斷floor(x),ceil(x),floor(y),ceil(y)任意組成的點的距離。
這個復雜度O(n)不慫。
你問我沒有SPJ這題怎樣做？
登陸main.edu.pl，弄到所有數據，求中位數的時候依照他的意思求，取左側或右側我忘了，答案坐標非整數判斷的時候依照他的意思取終究答案(好像是橫縱坐標最大)。
趕快來人寫SPJ！
代碼:
#include #include #include #include #include #include #define N 100100 #define eps 1e⑻ using namespace std; typedef long long ll; int n;
ll sum; struct node
{
ll x,y,t; friend istream& operator >> (istream &_,node &a)
{scanf("%lld%lld%lld",&a.x,&a.y,&a.t);sum+=a.t;return _;}
}pt[N]; mapint>mx,my; int totx,toty; struct arr
{
ll val,num;
}arrx[N],arry[N]; bool cmp(arr a,arr b)
{ return a.val5],yy[5]; int main()
{ #ifndef ONLINE_JUDGE freopen("mag.in","r",stdin);
freopen("mag.out","w",stdout); #endif scanf("%d",&n); for(int i=1;i<=n;i++)cin>>pt[i]; for(int i=1;i<=n;i++) { ll x=pt[i].x-pt[i].y,y=pt[i].x+pt[i].y; if(!mx[x])
mx[x]=++totx,arrx[totx].val=x,arrx[totx].num=pt[i].t; else arrx[mx[x]].num+=pt[i].t; if(!my[y])
my[y]=++toty,arry[toty].val=y,arry[toty].num=pt[i].t; else arry[my[y]].num+=pt[i].t;
}
sort(arrx+1,arrx+totx+1,cmp);
sort(arry+1,arry+toty+1,cmp); for(int i=1;i<=totx;i++)sumx[i]=sumx[i-1]+arrx[i].num; for(int i=1;i<=toty;i++)sumy[i]=sumy[i-1]+arry[i].num; int flag=0; if(!(sum&1))flag=1;
sum>>=1; double midX=0,midY=0; int l=1,r=totx,ans=0; while(l<=r) { int mid=(l+r)>>1; if(sumx[mid]<=sum)ans=mid,l=mid+1; else r=mid-1;
} if(flag)
{ if(sumx[ans]==sum)midX=arrx[ans].val; else midX=arrx[ans+1].val;
}else midX=arrx[ans+1].val;
l=1,r=toty,ans=0; while(l<=r) { int mid=(l+r)>>1; if(sumy[mid]<=sum)ans=mid,l=mid+1; else r=mid-1;
} if(flag)
{ if(sumy[ans]==sum)midY=arry[ans].val; else midY=arry[ans+1].val;
}else midY=arry[ans+1].val; double prex=(midX+midY)/2; double prey=(midY-midX)/2; if(prex-floor(prex)>eps||prey-floor(prey)>eps)
{
xx[1]=xx[2]=(ll)floor(prex),xx[3]=xx[4]=(ll)ceil(prex);
yy[1]=yy[3]=(ll)floor(prey),yy[2]=yy[4]=(ll)ceil(prey);
ll sum=-1,no; for(int i=1;i<=4;i++)
{
ll ret=0; for(int j=1;j<=n;j++) { ll tmpx=pt[j].x-xx[i],tmpy=pt[j].y-yy[i]; if(tmpx<0)tmpx=-tmpx;if(tmpy<0)tmpy=-tmpy;
ret+=pt[j].t*(max(tmpx,tmpy));
} if(sum==-1||ret<=sum) {sum=ret,no=i;} } printf("%lld %lld
",xx[no],yy[no]);
}else { printf("%lld %lld
",(ll)prex,(ll)prey);
}
}
