看心情填坑

http://codeforces.com/gym/100792/problem/G

既然刚才写了平面几何技巧，干脆来个二连发。

看n=20w和这个题意感觉应该是经典问题，看了半个小时一点想法都没有_(:зゝ∠)_然后被阳神训斥了_(:зゝ∠)_然后一下子就懂了_(:зゝ∠)_

题意:定义两点距离为($\sqrt{2}-1)$*max(abs(x[i]-x[j]),abs(y[i]-y[j]))+min(abs(x[i]-x[j]),abs(y[i]-y[j]))

然后求平面最远点对。

平面最远点对不是个经典nlog问题吗，看了一下这个和欧几里得距离不一样不会来_(:зゝ∠)_然后想了一下旋转45^。，发现并没有什么卵用，因为这个东西本来就是有45^。的路径的然后我整个人就懵逼了_(:зゝ∠)_

然后阳神就过来训斥了我_(:зゝ∠)_你这个东西不是O(n*8)的SB东西吗_(:зゝ∠)_

因为两点之间的距离中一共有3个不同的max或者min（abs也算作max(k,-k)),也就是说一共也就8种情况，因为两点之间的距离一定是8种情况里最大的一种，然后我们8种情况分别记录当前的最优点就行了。

怕没听懂还是写一下8种情况吧：

1、dis=($\sqrt{2}-1)$)*(x[i]-x[j])+y[i]-y[j];

2、dis=($\sqrt{2}-1)$)*(x[i]-x[j])+y[j]-y[i];

3、dis=($\sqrt{2}-1)$)*(x[j]-x[i])+y[i]-y[j];

4、dis=($\sqrt{2}-1)$)*(x[j]-x[i])+y[j]-y[i];

5、dis=($\sqrt{2}-1)$)*(y[i]-y[j])+x[i]-x[j];

6、dis=($\sqrt{2}-1)$)*(y[i]-y[j])+x[j]-x[i];

7、dis=($\sqrt{2}-1)$)*(y[j]-y[i])+x[i]-x[j];

8、dis=($\sqrt{2}-1)$)*(y[j]-y[i])+x[j]-x[i];

这样就很清晰了_(:зゝ∠)_单独对于每一种情况，在x[i]、y[i]相同的情况下，某个work(x[j],y[j])一定与dis有单调性，我们只要按照这个单调性维护最优点就行了_(:зゝ∠)_总复杂度空间O(1),时间O(n)

一边读一边做可以做到空间O(1)不想改了_(:зゝ∠)_