看心情填坑

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)

#include<cstdio>
#include<cmath>
using namespace std;
double t=sqrt(2)-1;
struct point{
    int x,y,k;
}p[200005],P[8];
int n,X,Y;
double ans;
double a[8]={t,1,t,1,-t,-1,-t,-1};
double b[8]={1,t,-1,-t,1,t,-1,-t};
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y),p[i].k=i;
    for(int i=0;i<8;i++)P[i]=p[1];
    ans=-1;
    for(int i=2;i<=n;i++){
        for(int j=0;j<8;j++){
            double s=(P[j].y-p[i].y)*b[j]+(P[j].x-p[i].x)*a[j];
            if(s>ans){
                X=P[j].k;
                Y=p[i].k;
                ans=s;
            }
        }
        for(int j=0;j<8;j++)if(p[i].x*a[j]+p[i].y*b[j]>P[j].x*a[j]+P[j].y*b[j])P[j]=p[i];
    }
    printf("%d %d\n",X,Y);
}

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