題目鏈接

https://codeforces.com/contest/685/problem/C

題解

我怎么又還差最后一步的時候放棄了然后往別的方向上想了一小時才發現這個思路能做……

首先二分答案，轉化為所有點半徑為\(mid\)的曼哈頓距離區域內是否有交。
考慮二維問題，顯然可以用曼哈頓轉切比雪夫來做，把\((x,y)\)變成\((x+y,x-y)\)那么原來兩點的曼哈頓距離就等于后來兩點的切比雪夫距離。考慮一下這個做法的證明: \[|x_1-x_2|+|y_1-y_2|=\max(x_1-x_2+y_1-y_2,x_1-x_2-y_1+y_2,-x_1+x_2+y_1-y_2,-x_1+x_2-y_1+y_2)=\max(|(x_1+y_1)-(x_2+y_2)|,|(x_1-y_1)-(x_2-y_2)|)\]
三維的問題也可以用類似的思路。\[|x_1-x_2|+|y_1-y_2|+|z_1-z_2|=\max(|(x_1+y_1+z_1)-(x_2+y_2+z_2)|,|(x_1-y_1+z_1)-(x_2-y_2+z_2)|,|(x_1+y_1-z_1)-(x_2+y_2-z_2)|,|(x_1-y_1-z_1)-(x_2-y_2-z_2)|)\]于是我們可以把\((x,y,z)\)變成一個四維的坐標\((x+y+z,x-y+z,x+y-z,x-y-z)\), 曼哈頓距離就變成了切比雪夫距離，求一下區間交就行了。但是有以下兩個附加限制：

(1) 新的坐標\((x,y,z,w)\)必須滿足\(w=y+z-x\).

(2) 由于題目里要求所有坐標都是整數，新的坐標\((x,y,z,w)\)必須滿足\(y-x,z-x\)都是\(2\)的倍數。
那么可以枚舉\(x,y,z,w\)都是奇數或偶數的情況，分別求一下在\(x,y,z\)取值范圍內\(y+z-x\)的最大最小值，然后和\(w\)的取值范圍求交，調整一下即可求解。
時間復雜度\(O(n\log C)\), \(C\)為值域。

代碼

#include<bits/stdc++.h> #define llong long long #define mkpr make_pair #define riterator reverse_iterator using namespace std;inline int read() {int x = 0,f = 1; char ch = getchar();for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}return x*f; }const int N = 1e5; const llong INF = 6e18+1; struct Point {llong x,y,z,w; } a[N+3]; int n;llong fun(llong x,llong y,llong z) {return x&1?x+z:x+y;}bool check(llong mid,bool typ=false) {llong lx = -INF,ly = -INF,lz = -INF,lw = -INF,rx = INF,ry = INF,rz = INF,rw = INF;for(int i=1; i<=n; i++){lx = max(lx,a[i].x-mid); rx = min(rx,a[i].x+mid);ly = max(ly,a[i].y-mid); ry = min(ry,a[i].y+mid);lz = max(lz,a[i].z-mid); rz = min(rz,a[i].z+mid);lw = max(lw,a[i].w-mid); rw = min(rw,a[i].w+mid);}if(lx>rx||ly>ry||lz>rz||lw>rw) return false;llong lx2 = fun(lx,0,1),ly2 = fun(ly,0,1),lz2 = fun(lz,0,1),lw2 = fun(lw,0,1),rx2 = fun(rx,0,-1),ry2 = fun(ry,0,-1),rz2 = fun(rz,0,-1),rw2 = fun(rw,0,-1);if(lx2<=rx2&&ly2<=ry2&&lz2<=rz2&&lw2<=rw2){llong lw3 = ly2+lz2-rx2,rw3 = ry2+rz2-lx2;if(max(lw2,lw3)<=min(rw2,rw3)){llong w = max(lw2,lw3),x = rx2,y = ly2,z = lz2;if(typ){if(y+z-x<w) {y += min(ry2-ly2,w-(y+z-x));}if(y+z-x<w) {z += min(rz2-lz2,w-(y+z-x));}if(y+z-x<w) {x -= min(rx2-lx2,w-(y+z-x));}llong xx = (y+z)/2ll,yy = (x-y)/2ll,zz = (x-z)/2ll;printf("%I64d %I64d %I64d\n",xx,yy,zz);}return true;}}lx2 = fun(lx,1,0),ly2 = fun(ly,1,0),lz2 = fun(lz,1,0),lw2 = fun(lw,1,0),rx2 = fun(rx,-1,0),ry2 = fun(ry,-1,0),rz2 = fun(rz,-1,0),rw2 = fun(rw,-1,0);if(lx2<=rx2&&ly2<=ry2&&lz2<=rz2&&lw2<=rw2){llong lw3 = ly2+lz2-rx2,rw3 = ry2+rz2-lx2;if(max(lw2,lw3)<=min(rw2,rw3)){if(typ){llong w = max(lw2,lw3),x = rx2,y = ly2,z = lz2;if(y+z-x<w) {y += min(ry2-ly2,w-(y+z-x));}if(y+z-x<w) {z += min(rz2-lz2,w-(y+z-x));}if(y+z-x<w) {x -= min(rx2-lx2,w-(y+z-x));}llong xx = (y+z)/2ll,yy = (x-y)/2ll,zz = (x-z)/2ll;printf("%I64d %I64d %I64d\n",xx,yy,zz);}return true;}}return false; }int main() {int T; scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=1; i<=n; i++){llong x,y,z; scanf("%I64d%I64d%I64d",&x,&y,&z);a[i].x = x+y+z,a[i].y = x-y+z,a[i].z = x+y-z,a[i].w = x-y-z;}llong left = 0ll,right = 3e18;while(left<right){llong mid = left+(right-left>>1);if(check(mid)) {right = mid;}else {left = mid+1;}} // printf("ans=%I64d\n",right);check(right,true);}return 0; }

總結

以上是生活随笔為你收集整理的Codeforces 685C Optimal Point (二分、不同类型距离的相互转换)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。