Description
Mirko准备带他所有的朋友去Zaz演唱会。他已经拿到了票，现在在回去派送门票的路上。
Mirko朋友的住所都可以用直角坐标系来表示。他在走路的时候，只能经过整数坐标点。他走一步可以移动到相邻的八个整数坐标点（上，下，左，右，上左，下左，上右，下右）。
Mirko的每个朋友住在一些整数坐标点（x，y）上，而且愿意走一段距离去见Mirko。具体来说，Mirko可以在离他朋友家里不超过P步的地方见他的朋友，P取决于他朋友的慵懒程度。
当他完成派送门票的事后，Mirko回想起了他见朋友的顺序。计算Mirko在这段路上走的最少可能的步数。Mirko的起始点和终止点是未知的。
Solution
注意到起点是没有什么意义的，我们只关注在最优答案的情况下的终点集合 \(S\)。
注意到终点会形成一个矩形，因此只用记录左下和右上的坐标即可。
对于 \(i-1\) 的终点集合 \(S\) 和第 \(i\) 个正方形，二分 \(len\)，同时更新终点集合 \(S\)。
二分合法条件是将集合扩张 \(mid\) 后与第 \(i\) 个正方形有交集，同时更新后的终点集合就是这个交集。
复杂度 \(\mathcal O(n\log 200000)\)，当然也可以不二分，用数学的方法做到 \(\mathcal O(n)\)。
Code
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll n,x,y,z,len,ans;
struct node
{
ll x1,y1,x2,y2;
}a,b;
node kuo(node a,ll l)
{
a.x1-=l;a.y1-=l;
a.x2+=l;a.y2+=l;
return a;
}
node jiao(node x,node y)
{
node s;
s.x1=max(x.x1,y.x1);
s.y1=max(x.y1,y.y1);
s.x2=min(x.x2,y.x2);
s.y2=min(x.y2,y.y2);
return s;
}
bool check(node x) {return x.x1<=x.x2&&x.y1<=x.y2;}
int erfen(node x,node y)
{
ll l=0,r=200000,mid,res=0;
while (l<=r)
{
mid=(l+r)>>1;
if (check(jiao(kuo(x,mid),y))) res=mid,r=mid-1;
else l=mid+1;
}
return res;
}
int main()
{
scanf("%lld",&n);
scanf("%lld%lld%lld",&x,&y,&z);
a.x1=x-z;a.y1=y-z;
a.x2=x+z;a.y2=y+z;
for (int i=2;i<=n;++i)
{
scanf("%lld%lld%lld",&x,&y,&z);
b.x1=x-z;b.y1=y-z;
b.x2=x+z;b.y2=y+z;
len=erfen(a,b);
a=jiao(kuo(a,len),b);
ans+=len;
}
printf("%lld\n",ans);
return 0;
}