题意
三维空间内给n个点，求一个整点使得到所有点的最大曼哈顿距离最小。
n
≤
1
0
5
n\le10^5
n≤105
思路
很容易想到二分判定，然后可行域求交。假如是二维的话旋转一下很好做。三维的话旋转不好想象，不如直接用更本质的数学方法。考虑可行域如何表示，二维下只需要四条不等式，三维下需要八条。做一些换元和奇偶讨论即可。具体可参照题解
O
(
n
log
x
)
O(n\log x)
O(nlogx)
#include <bits/stdc++.h>
#define max(a,b) ((a) > (b) ? (a) : (b))
using namespace std
;
const int N
= 1e5 + 10;
typedef long long ll
;
const ll inf
= 4e18;
int T
, n
;
ll x
[N
], y
[N
], z
[N
];
ll ansx
, ansy
, ansz
;
void upp(ll
&x
) {
ll i
= 0; for(i
= x
/ 2 - 3; i
* 2 < x
; i
++);
x
= i
;
}
void don(ll
&x
) {
ll i
= 0; for(i
= x
/ 2 + 3; i
* 2 > x
; i
--);
x
= i
;
}
bool ok(ll dis
) {
for(int r
= 0; r
< 2; r
++) {
ll amin
= -inf
, amax
= inf
;
ll bmin
= -inf
, bmax
= inf
;
ll cmin
= -inf
, cmax
= inf
;
ll smin
= -inf
, smax
= inf
;
for(int i
= 1; i
<= n
; i
++) {
amin
= max(amin
, ( x
[i
] + y
[i
] - z
[i
] - dis
- r
));
bmin
= max(bmin
, ( x
[i
] - y
[i
] + z
[i
] - dis
- r
));
cmin
= max(cmin
, (-x
[i
] + y
[i
] + z
[i
] - dis
- r
));
smin
= max(smin
, ( x
[i
] + y
[i
] + z
[i
] - dis
- 3 * r
));
amax
= min(amax
, ( x
[i
] + y
[i
] - z
[i
] + dis
- r
));
bmax
= min(bmax
, ( x
[i
] - y
[i
] + z
[i
] + dis
- r
));
cmax
= min(cmax
, (-x
[i
] + y
[i
] + z
[i
] + dis
- r
));
smax
= min(smax
, ( x
[i
] + y
[i
] + z
[i
] + dis
- 3 * r
));
}
upp(amin
), don(amax
);
upp(bmin
), upp(cmin
), upp(smin
);
don(bmax
), don(cmax
), don(smax
);
if (amin
> amax
|| bmin
> bmax
|| cmin
> cmax
|| smin
> smax
) {
continue;
}
ll sum
= amin
+ bmin
+ cmin
;
if (sum
> smax
) continue;
if (sum
- amin
+ amax
>= smin
) {
ll a
= amin
+ max(0, smin
- sum
);
ll b
= bmin
;
ll c
= cmin
;
ansx
= a
+ b
+ r
;
ansy
= a
+ c
+ r
;
ansz
= b
+ c
+ r
;
return 1;
} else {
sum
+= amax
- amin
;
if (sum
- bmin
+ bmax
>= smin
) {
ll a
= amax
;
ll b
= bmin
+ max(0, smin
- sum
);
ll c
= cmin
;
ansx
= a
+ b
+ r
;
ansy
= a
+ c
+ r
;
ansz
= b
+ c
+ r
;
return 1;
} else {
sum
+= bmax
- bmin
;
if (sum
- cmin
+ cmax
>= smin
) {
ll a
= amax
;
ll b
= bmax
;
ll c
= cmin
+ max(0, smin
- sum
);
ansx
= a
+ b
+ r
;
ansy
= a
+ c
+ r
;
ansz
= b
+ c
+ r
;
return 1;
}
}
}
}
return 0;
}
#define abs(x) ((x) > 0 ? (x) : -(x))
void check() {
ll mx
= 0;
for(int i
= 1; i
<= n
; i
++) {
mx
= max(mx
, abs(ansx
- x
[i
]) + abs(ansy
- y
[i
]) + abs(ansz
- z
[i
]));
}
cerr
<< mx
<< endl
;
}
int main() {
int g
= clock();
freopen("c.in", "r", stdin);
freopen("c.out","w", stdout);
for(cin
>>T
;T
;T
--) {
scanf("%d", &n
);
for(int i
= 1; i
<= n
; i
++) {
scanf("%I64d %I64d %I64d", &x
[i
], &y
[i
], &z
[i
]);
}
ll l
= 0, r
= 3e18;
int cnt
= 0;
while (l
<= r
) {
if (ok(l
+ r
>> 1)) {
r
= (l
+ r
>> 1) - 1;
} else {
l
= (l
+ r
>> 1) + 1;
}
}
check();
printf("%I64d %I64d %I64d\n", ansx
, ansy
, ansz
);
}
cerr
<< clock() - g
<< endl
;
}
