C++

#include <cstdio>

#include <cstdlib>

#include <climits>

#include <algorithm>

using namespace std;

struct Pos{

    int x;

    int y;

    int idx;

};

 

int N;

long long x_[500010],y_[500010];

Pos pos_x[500010];

Pos pos_y[500010];

long long dist[500010];

int comp_x(Pos a,Pos b){

    if(a.x==b.x){

        return a.y<b.y;

    }

    return a.x<b.x;

}

int comp_y(Pos a,Pos b){

    if(a.y==b.y){

        return a.x<b.x;

    }

    return a.y<b.y;

}

int main()

{

    scanf("%d",&N);

    for(int i=1;i<=N;i++){

        int a,b;

        scanf("%d %d",&a,&b);

        pos_x[i].x=a;

        pos_x[i].y=b;

        pos_x[i].idx=i;

        pos_y[i].x=a;

        pos_y[i].y=b;

        pos_y[i].idx=i;

    }

    sort(pos_x+1,pos_x+N+1,comp_x);

    sort(pos_y+1,pos_y+N+1,comp_y);

    for(int i=1;i<=N;i++){

        x_[i]=pos_x[i].x+x_[i-1];

        y_[i]=pos_y[i].y+y_[i-1];

    }

    long long min_=LLONG_MAX;

    int result=0;

    for(int i=1;i<=N;i++){

        int idx_x=pos_x[i].idx;

        int idx_y=pos_y[i].idx;

        dist[idx_x]+=(long long)pos_x[i].x*(i-1)-x_[i-1]+x_[N]-x_[i]-(long long)pos_x[i].x*(N-i);

        dist[idx_y]+=(long long)pos_y[i].y*(i-1)-y_[i-1]+y_[N]-y_[i]-(long long)pos_y[i].y*(N-i);

    }

    for(int i=1;i<=N;i++){

        //printf("%lld\n",dist[i]);

        if(dist[i]<min_){

            result=i;

            min_=dist[i];

        }

    }

    printf("%d",result);

    return 0;

}