Codeforces 120 J. Minimum Sum

問題

n本のベクトルが与えられる。
それぞれのベクトルv=(x,y)に対して次のような変換を施してよい。
v1=(x,y)
v2=(-x,y)
v3=(x,-y)
v4=(-x,-y)


このとき|v[i]+v[j]|が最小となるようなi,jおよびそのときの変換を求めよ。
答えが複数あるときはどれを出力してもかまわない。

制約条件

n≦10^5
座標の絶対値は10000以下

方針

全てのベクトルの終点を第一象限に移動する。
すると、この問題はn個の点の最近点対を求める問題となる。


最近点対はO(nlog n)で求めることが可能である(らしい、アルゴリズムまだ理解してない)。

ソースコード

最近点対はspaghetti sourceより。

const double EPS = 1e-8;
const double INF = 1e12;
typedef complex<double> P;
namespace std {
  bool operator < (const P& a, const P& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}
double cross(const P& a, const P& b) {
  return imag(conj(a)*b);
}
double dot(const P& a, const P& b) {
  return real(conj(a)*b);
}
pair<P,P> closestPair(vector<P> p) {
  int n = p.size(), s = 0, t = 1, m = 2, S[n]; S[0] = 0, S[1] = 1;
  sort(all(p)); // "p < q" <=> "p.x < q.x"
  double d = norm(p[s]-p[t]);
  for (int i = 2; i < n; S[m++] = i++) rep(j, m) {
    if (norm(p[S[j]]-p[i])<d) d = norm(p[s = S[j]]-p[t = i]);
    if (real(p[S[j]]) < real(p[i]) - d) S[j--] = S[--m];
  }
  return make_pair( p[s], p[t] );
}

int n;
map<P,int> dir,id;

void run(){
  cin>>n;
  vector<P> ps;
  rep(i,n){
    int x,y,k; cin>>x>>y;
    if(x>=0&&y>=0)k=1;
    else if(x<=0&&y>=0)k=2;
    else if(x>=0&&y<=0)k=3;
    else k=4;
    x=abs(x); y=abs(y);
    if(dir.count(P(x,y))){
      cout<<id[P(x,y)]+1<<" "<<dir[P(x,y)]<<" "<<i+1<<" "<<5-k;
      return;
    }
    dir[P(x,y)]=k; id[P(x,y)]=i;
    ps.pb(P(x,y));
  }
  pair<P,P> ans=closestPair(ps);
  P a=ans.first, b=ans.second;
  cout<<id[a]+1<<" "<<dir[a]<<" "<<id[b]+1<<" "<<5-dir[b]<<endl;
}