题解 CF685C 【Optimal Point】
chen_zhe
2020-04-19 21:26:37
# CF685C Optimal Point
这个题，我看到的第一眼以为是个三分。因为 $x$ 轴固定一个位置，$y$ 轴固定一个位置，去扫 $z$ 轴，会发现距离是一个单峰的函数，对于 $x$ 轴和 $y$ 轴也类似处理，类似 [UVA10228](https://www.luogu.com.cn/problem/UVA10228) 的处理方式即可。那么我们得到了一个 $O(n \log^3 v)$ 的做法，而且是正确的。但是看一眼数据规模，$n=10^5,v=10^{18}$，会被卡掉，这就很令人不爽。
然后我们看一眼题意，它是要求距离的最大值最小，而最大值最小又可以提示我们这个题可能需要二分，那么我们就可以很显然地去二分这个最大距离 $dis$，然后就有 $n$ 组约束条件 $|x-x_i|+|y-y_i|+|z-z_i| \leq dis$
我们会发现这是个很不好处理的不等式关系组，因为有一堆变量，还套个绝对值。我们考虑拆绝对值，根据正负关系，应该会得到 $2^3=8$ 组不等式关系：
$\begin{cases}x+y+z-x_i-y_i-z_i \leq dis \\ x+y-z-x_i-y_i+z_i \leq dis \\ x-y+z-x_i+y_i-z_i \leq dis \\ x-y-z-x_i+y_i+z_i \leq dis \\ -x+y+z+x_i-y_i-z_i \leq dis \\ -x+y-z+x_i-y_i+z_i \leq dis \\ -x-y+z+x_i+y_i-z_i \leq dis \\ -x-y-z+x_i+y_i+z_i \leq dis\end{cases}$
看起来是组很恐怖的式子。考虑移项合并，则有：
$\begin{cases} l_1 \leq x+y+z \leq r_1 \\ l_2 \leq -x+y+z \leq r_2 \\ l_3 \leq x-y+z \leq r_3 \\ l_4 \leq x+y-z \leq r_4\end{cases}$
其中 $l_{1 \dots 4},r_{1 \dots 4}$ 在后续计算中可被视作常数，分别为：
$\begin{cases}l_1=\max(-mid+x_i+y_i+z_i)\\l_2=\max(-mid-x_i+y_i+z_i)\\l_3=\max(-mid+x_i-y_i+z_i)\\l_4=\max(-mid+x_i+y_i-z_i)\end{cases}$
$\begin{cases}r_1=\min(-mid+x_i+y_i+z_i)\\r_2=\min(-mid-x_i+y_i+z_i)\\r_3=\min(-mid+x_i-y_i+z_i)\\r_4=\min(-mid+x_i+y_i-z_i)\end{cases}$
这里的 $\max()$ 和 $\min()$ 其实本质上是给区间取交集。
我们考虑换元，令 $a=-x+y+z,b=x-y+z,c=x+y-z$，那么可以代换出
$\begin{cases}x=\frac{b+c}{2}\\y=\frac{a+c}{2}\\z=\frac{a+b}{2}\\x+y+z=a+b+c\end{cases}$
我们还会发现另外一点，就是 $a,b,c$ 的奇偶性是一致的，因为 $a,b,c$ 的奇偶性取决于 $x,y,z$ 的奇偶性，符号只是增加或者减少了两倍的 $x$ 或 $y$ 或 $z$，不影响对 $2$ 取模的余数。这也就告诉了我们，其实我们可以去枚举 $a \bmod 2$，这样可以再换元：
$\begin{cases}a'=\frac{a-a\bmod 2}{2} \\ b'=\frac{b-a\bmod 2}{2} \\ c'=\frac{c-a\bmod 2}{2}\end{cases}$
这样我们再带回第二个不等式组，则有：
$\begin{cases}l_1' \leq a'+b'+c' \leq r_1' \\ l_2' \leq a' \leq r_2'\\ l_3' \leq b' \leq r_3' \\ l_4' \leq c' \leq r_4'\end{cases}$
那么问题就在于如何求解这个不等式组了。其实也不要想得太复杂，因为我们只要求出一组解，所以可以考虑我们平时做数学题的策略：令 $a'=l_2',b'=l_3',c'=l_4'$，这样可以保证后三个不等式的约束，然后再看这个时候的 $a'+b'+c'$ 是否满足 $l_1' \leq a'+b'+c' \leq l_2'$，若满足就是一组解；
若不满足条件，而且 $a'+b'+c' < l_1'$，我们就可以考虑，在不超过后三组约束条件的同时，适当增加一下 $a',b',c'$ 的大小，也就是先加 $a'$，如果 $a'$ 被加到最大还不满足 $l_1'$，就去加 $b'$，以此类推即可。如果是 $a'+b'+c' > r_1'$ 那么就无解了。
最后的时间复杂度应该是 $O(n \log_2 v)$ 了，比开场的那个三分不知道快到哪里去了。注意一下 C++ 特色取模可能造成一些意想不到的诡异问题。
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <queue>
#include <vector>
using namespace std;
inline long long read()
{
long long x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n;
long long x[100050],y[100050],z[100050],xans,yans,zans;
inline void Init()
{
for (int i=1;i<=n;i++)
x[i]=y[i]=z[i]=0;
//memset(x,0,sizeof(x));
//memset(y,0,sizeof(y));
//memset(z,0,sizeof(z));
xans=yans=zans=0;
}
inline bool check(long long mid)
{
long long r1=4e18,r2=4e18,r3=4e18,r4=4e18;
long long l1=-4e18,l2=-4e18,l3=-4e18,l4=-4e18;
for (int i=1;i<=n;i++)
{
r1=min(r1,mid+x[i]+y[i]+z[i]);
r2=min(r2,mid-x[i]+y[i]+z[i]);
r3=min(r3,mid+x[i]-y[i]+z[i]);
r4=min(r4,mid+x[i]+y[i]-z[i]);
l1=max(l1,-mid+x[i]+y[i]+z[i]);
l2=max(l2,-mid-x[i]+y[i]+z[i]);
l3=max(l3,-mid+x[i]-y[i]+z[i]);
l4=max(l4,-mid+x[i]+y[i]-z[i]);
}
for (int i=0;i<=1;i++)
{
long long l11=l1+((l1&1)^i);
long long r11=r1-((r1&1)^i);
long long l21=l2+((l2&1)^i);
long long r21=r2-((r2&1)^i);
long long l31=l3+((l3&1)^i);
long long r31=r3-((r3&1)^i);
long long l41=l4+((l4&1)^i);
long long r41=r4-((r4&1)^i);
if (l11<=r11 && l21<=r21 && l31<=r31 && l41<=r41)
{
long long a=l21;
long long b=l31;
long long c=l41;
if (a+b+c<=r11)
{
if (a+b+c<l11)
{
if (r21<l11-b-c)
a=r21;
else
a=l11-b-c;
}
if (a+b+c<l11)
{
if (r31<l11-a-c)
b=r31;
else
b=l11-a-c;
}
if (a+b+c<l11)
{
if (r41<l11-a-b)
c=r41;
else
c=l11-a-b;
}
if (a+b+c>=l11)
{
xans=(b+c)>>1;
yans=(a+c)>>1;
zans=(a+b)>>1;
return 1;
}
}
}
}
return 0;
}
int main()
{
int T=read();
while (T--)
{
n=read();
Init();
for (int i=1;i<=n;i++)
{
x[i]=read();
y[i]=read();
z[i]=read();
}
if (n==1)
{
cout << x[1] << " " << y[1] << " " << z[1] << endl;
continue;
}
long long left=0,right=4e18;
while (left<=right)
{
long long mid=(left+right)>>1;
if (check(mid))
right=mid-1;
else
left=mid+1;
}
cout << xans << " " << yans << " " << zans << endl;
}
return 0;
}
```