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; }