120J - Minimum Sum - CodeForces Solution

#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
int Read()
{
    int Output=0,W=1;
    char Input=getchar();
    while(Input<'0'||Input>'9')
    {
        if(Input=='-')W=-1;
        Input=getchar();
    }
    while(Input>='0'&&Input<='9')
    {
        Output=Output*10+Input-'0';
        Input=getchar();
    }
    return Output*W;
}
const int Inf=1e9;
int N,Cnt;
struct point
{
    int X,Y;
    int Posi,K;
}Point[400001],Replace[400001];
int Stack[400001];
int Tot;
int Ans=Inf;
point Ansa,Ansb;
void Make(int X,int Y,int Posi,int K)
{
    Point[++Cnt].X=X;
    Point[Cnt].Y=Y;
    Point[Cnt].Posi=Posi;
    Point[Cnt].K=K;
}
bool Cmp(point A,point B)
{
    return A.X<B.X;
}
int Distance(point A,point B)
{
    return ((A.X-B.X)*(A.X-B.X)+(A.Y-B.Y)*(A.Y-B.Y));
}
void Merge(int L,int Mid,int R)
{
    int Left=L,Right=Mid+1;
    for(int i=L;i<=R;++i)
    {
        if(Left>Mid)Replace[i]=Point[Right++];
        else if(Right>R)Replace[i]=Point[Left++];
        else if(Point[Left].Y<Point[Right].Y)Replace[i]=Point[Left++];
        else Replace[i]=Point[Right++];
    }
    for(int i=L;i<=R;++i)
    Point[i]=Replace[i];
}
void Work(int L,int R)
{
    #define Mid ((L+R)>>1)
    if(L==R)return;
    point Middle=Point[Mid];
    Work(L,Mid),Work(Mid+1,R);
    Merge(L,Mid,R);
    Tot=0;
    for(int i=L;i<=R;++i)
    if((Point[i].X-Middle.X)*(Point[i].X-Middle.X)<=Ans)
    Stack[++Tot]=i;
    for(int i=1;i<=Tot;++i)
    {
        for(int j=i+1;j<=Tot;++j)
        {
            if((Point[Stack[i]].Y-Point[Stack[j]].Y)*(Point[Stack[i]].Y-Point[Stack[j]].Y)>Ans)
            break;
            if(Point[Stack[i]].Posi==Point[Stack[j]].Posi)
            continue;
            int Dis=Distance(Point[Stack[i]],Point[Stack[j]]);
            if(Dis<Ans)
            {
                Ans=Dis;
                Ansa=Point[Stack[i]],Ansb=Point[Stack[j]];
            }
        }
    }
    #undef Mid
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    N=Read();
    for(int i=1;i<=N;++i)
    {
        int X=Read(),Y=Read();
        Make(X,Y,i,1),Make(-X,Y,i,2);
        Make(X,-Y,i,3),Make(-X,-Y,i,4);
    }
    sort(Point+1,Point+Cnt+1,Cmp);
    Work(1,Cnt);
    printf("%d %d %d %d",Ansa.Posi,Ansa.K,Ansb.Posi,5-Ansb.K);
}