5

2 つの円があり、それらの中心は固定されており、入力として与えられます。次に、n 個の点があり、その x 座標と y 座標が入力として与えられます。

最後に、q 個のクエリがあります。クエリごとに、2 つの円の半径 (r1 と r2 とする) が与えられます。各クエリの最初の円または 2 番目の円内のポイントの総数を出力します。ポイントから中心までの距離が円の半径以下の場合、ポイントは円の内側にあります。

制約: n, q <= 10^6 r1,r2 <= 10^7 および各座標に対して |x| と |y| <= 10^6

O(nlogn) または O(nlog^2n) の前処理と、クエリごとの O(logn) アルゴリズムを探しています。クエリごとの O(n) ソリューションは遅すぎます。これをクラックする方法はありますか？

4

2 に答える 2

4

O（log 2 N）クエリ時間のソリューション。

  1. 各クエリで両方の円の外側のポイントをカウントし、ポイントの総数から結果を差し引く方が簡単です。
  2. デカルト座標を使用する方が簡単です。したがって、XはC1からの距離、YはC2からの距離になります。この場合、エリア内のポイントの数を見つけるだけで済みますX > r1 && Y > r2。
  3. 各ポイントに値「1」を割​​り当てます。これで、指定された領域の値の合計を見つけるだけで済みます。1Dの場合、これはフェンウィックツリーで行うことができます。ただし、2Dフェンウィックツリーを使用する場合、2Dの場合はそれほど変わりません。
  4. 2Dフェニック木はあまりにも多くのスペースを占める必要があります（与えられた制約で10 12の値）。ただし、フェニックツリーの2D配列は非常にまばらであるため、ハッシュマップを使用してその値を格納し、必要なスペース（および前処理時間）をO（N log 2 N）に減らすことができます。
于 2013-03-05T10:37:24.363 に答える
2

C1、C2 をディスクの中心とします。Pi、i = 1 ... n を点とします。Qj, j = 1 ... q を j 番目のクエリ Qj = (qj1, qj2) とする。

  1. 各点 Pi について、d(Pi, Ck)、k = 1 または 2 を計算します。それを並べ替えられたマルチマップに入れます。Mk(d(Pi, Ck)) には Pi が含まれます。これは O(nlogn) で実行できます (これは実際には、距離のリストをソートするのと同じです)。
  2. 各クエリ Qj に対して、Mk のキーで qjk のバイナリ検索を実行します。これは O(logn) で実行できます。
  3. クエリ Qj ごとに、上記で見つけたキー以下のキーで multimap の値の和集合を取ります。
于 2013-03-05T09:30:52.940 に答える