Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2385-a1f9024b
この記事にトラックバックする(FC2ブログユーザー)

UVa 12536 - Optimal Spaceway (この記事を編集する[管理者用])

Source

An Asian Regional contest to be decided, ACM ICPC Hatyai Regional Contest 2012 Semilive (2012-11-18)
UVa 12536

問題概要

2次元平面上のN個 (10000以下) の点が与えられる.
まず,それぞれの点との距離の二乗和を最小にする直線を求める問題.(距離の二乗和のみ答える)
その後,Q個 (100以下) のクエリに答える問題.
各クエリは,N個のうちの1点kと,その重みMが与えられるので,
 kまでの距離の二乗 * M + その他の点まで距離の二乗和
を最小にする直線を求める.(和のみを答える)

解法

要するに各クエリに対してO(N)で答えられれば良い.(最初のはM=1とすれば良い)
最小二乗法 (y座標の差の2乗和を最小にするやつ) で直線を求め,その直線がx軸に平行になるように,各点を回転するというのを繰り返し,
最小二乗法で求まる直線がx軸に十分平行に近くなるまで行った.
その際,毎回愚直に計算するとTLE.
最小二乗法では,直線を求めるのに必要なのは
 x座標の和,y座標の和,(x座標)^2の和,(y座標)^2の和,(x座標)*(y座標)の和
等なので,それらを1回求めておくと,回転した後の上の5つの値は回転角から計算可能.
なので,毎回回転させなくてもよく,直線を求めるだけならO(1)でできる.
なので各クエリに対して,上の計算は1回のみで良い.(または最初に1回だけ計算しておけば良い)
また,距離の二乗和も十分平行に近くなった時のみ計算すると各クエリに対して1回のみ計算すれば良い.
もっと良い方法がある気もする.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2385-a1f9024b
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。