数组$preX/Y[i]$表示前缀和

首先令$t=\frac{m}{n}$

然后答案改写可以写为

$\sum\limits_{i=1}^{q}{x^{'}_{i}-preX[q]+preX[n]t}$

$Y$同理

然后取平均值可以消去$x^{'}$

其中$m=nt+q$

然后答案表示为

$abs(x-preX[n]t-preX[q])+abs(y-preY[n]t-preY[q])-k(nt+q)\le 0$

然后枚举$q\in[1,n]$

再对$t$进行三分找到最小值，如果最小值小于等于0那么一定有答案，但是不能确定是否最小，于是又可以再在找到最小值的点作为右端点，0为左端点做一次二分答案，更新即可