ひとりで勝手にはじめた蟻本読書会 ギリギリを考える計算幾何 蟻本読書会 の続きです。
Coneology (POJ No.2932)
2次元平面上にN個の円があります。i番目の円は中心が（x_i, y_i）で半径がr_iであり、これらの円は互いに共有点を持ちません。最も外側にある円をすべて求めよ。
入力されるデータ
N
r_1 x_1 y_1
r_2 x_2 y_2
…
r_N x_N y_N
（ただし、1 ≦ N ≦ 40000 ）
どの点も共有点を持たないのである円が別の円の内部に含まれているかどうかの判定は、2 円の中心の距離と円の半径を比較することで可能です。
|
1 2 3 4 5 6 7 8 9 10 11 |
static double[] X; static double[] Y; static double[] R; // 円 i が円 j の内側にあるか判定する static bool IsInside(int i, int j) { double dx = X[i] - X[j]; double dy = Y[i] - Y[j]; return dx * dx + dy * dy <= R[j] * R[j]; } |
平面走査とは走査線という直線を動かしながら、走査線と交わる部分の情報を少しずつ更新していくことにより全体の計算をおこないます。
この問題の場合、Y軸に平行な走査線を左から右へ動かしつつ、もっとも外側にある円のうちで走査線と交わっているものの一覧を更新していくことを考えます。走査線を左から右へ動かした場合、円との交わりが変更されるのは走査線が円の左側か右側にきたときに限定されます。
ある円の左側に走査線がきたときには、その円がすでに走査線と交わっているものの一覧内の円に含まれているか判定しなければなりません。このとき実際に判定処理をおこなう必要があるのはその円からみて上下それぞれの方向で一番近い円だけで構わないことに気が付きます。もしその円がY座標が一番近い円には含まれず、ふたつ以上離れた円には含まれる場合、ふたつの円が交わってしまうからです。
ここでは指定されたY座標から上方向と下方向で一番近い円を取得できるデータ構造が必要です。要素を追加するときにソートされた状態を維持できるように二分探索法で挿入位置を取得します。またY座標が一番近い円を取得するときも二分探索法で該当する円を探します。
Eventクラス
走査線を移動させていくわけですが、そのX座標と格納されている座標はどの円の座標なのか？円の左側なのか右側なのかがわかるようにしておきます。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Event { public Event(double x, int circleID, bool isLeft) { X = x; CircleID = circleID; IsLeft = isLeft; } public double X = 0; // X 座標 public bool IsLeft = false; // 円の左側か？ public int CircleID = 0; // どの円の左右の座標か？ } |
Pairクラス
円のY座標を格納します。同時にどの円のY座標なのかがわかるようにしています。
|
1 2 3 4 5 6 7 8 9 10 |
class Pair { public Pair(int circleID, double y) { CircleID = circleID; Y = y; } public int CircleID = 0; public double Y = 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
class Program { static double[] X; static double[] Y; static double[] R; static List<Pair> Outer = new List<Pair>(); // 円 i が円 j の内側にあるか判定する static bool IsInside(int i, int j) { double dx = X[i] - X[j]; double dy = Y[i] - Y[j]; return dx * dx + dy * dy <= R[j] * R[j]; } // 指定された要素以上の値が現れる最小のインデックスを返す static int LowerBound(double target) { if (Outer[0].Y >= target) return 0; int left = 0; int right = Outer.Count; while (right - left > 1) { int mid = (left + right) / 2; if (target <= Outer[mid].Y) right = mid; else left = mid; } return right; } static void Main() { int N = int.Parse(Console.ReadLine()); List<Event> events = new List<Event>(); X = new double[N]; Y = new double[N]; R = new double[N]; for (int i = 0; i < N; i++) { double[] vs = Console.ReadLine().Split().Select(_ => double.Parse(_)).ToArray(); double r = vs[0]; double x = vs[1]; double y = vs[2]; X[i] = x; Y[i] = y; R[i] = r; events.Add(new Event(x - r, i, true)); // 走査線にかんする情報を格納する events.Add(new Event(x + r, i, false)); } // 走査線を左から右で移動させていくのでX座標でソートしておく events = events.OrderBy(_ => _.X).ToList(); List<int> rets = new List<int>(); // 結果を格納する foreach (Event ev in events) // 走査線を移動させていく { int id = ev.CircleID; // 走査線が円の左にある場合は、その円がOuterに登録されている円の内側にあるか判定する // 円の内部にないのであれば一番外側の円なので、 // その番号を結果を表示するリストに格納するとともにY座標をOuterに登録する // 走査線が円の右にある場合は、その円がOuterに登録されている円であるなら // Outerから削除する。登録されていないなら何もしない if (ev.IsLeft) { if (Outer.Count() == 0) { rets.Add(ev.CircleID); Pair pair = new Pair(id, Y[id]); Outer.Add(pair); continue; } int index = LowerBound(Y[id]); // 円 id がOuterに登録されている円の内側にあるか判定する if (index > 0) { // 上（Y座標が現在の円よりも小さいもののなかで最も近いもの） if (IsInside(id, Outer[index - 1].CircleID)) continue; } if (index < Outer.Count) { // 下（Y座標が現在の円よりも大きいもののなかで最も近いもの） if (IsInside(id, Outer[index].CircleID)) continue; } rets.Add(ev.CircleID); // ソートされた状態を維持したまま追加したいのでLowerBoundが返した位置に挿入する Pair pair2 = new Pair(id, Y[id]); Outer.Insert(index, pair2); } else { // 走査線が円の右にきたので、その円がOuterに登録されている場合はOuterから削除する // Outer.Count == 0 なら登録されていない。Outer[index].CircleID != id の場合も // 登録されていないので何もしない。 if (Outer.Count > 0) { int index = LowerBound(Y[id]); if (index < Outer.Count && Outer[index].CircleID == id) Outer.RemoveAt(index); } } } Console.WriteLine(rets.Count); Console.WriteLine(string.Join(" ", rets.Select(_ => _ + 1))); // 番号は1から始まるので } } |
G – 村
似たような問題がAtCoderにあります。
きつねのしえるは休暇でとある小さな村を訪れている。彼女が驚いたのはその村の表札がもつ性質である。
村には N 個の家屋がある。簡単のため村は 2 次元平面であるとし、家屋はこの平面上の点であると見なす。それぞれの家屋には表札が 1 個設けられており、その家の苗字を表していた。しえるは村の中を訪問するにつれてこの村の表札が次のような性質を持っていることに気付いた。
ある実数 R が存在する。
もし 2 つの家屋の距離が R 以下であるなら、その 2 つの家屋は同じ表札を持つ。
もし 2 つの家屋の距離が 3R 以上であるなら、その 2 つの家屋は異なる表札を持つ。
任意の 2 つの家屋の距離は R 以下であるか 3R 以上であるかのどちらかである。
距離は平面上のユークリッド距離によって計測するものとする。しえるはこの村に表札が全部で何種類あるのかが気になったが、この村は意外に広いということに気付いたので、計算機を使ってこの答えを模索することにした。
入力されるデータ
N R
x_1 y_1
x_2 y_2
…
x_N y_N（ただし、1 ≦ N ≦ 2 * 10^5
1 ≦ R ≦ 10^3
|x_i|, |y_i| ≦ 10^6
N は整数である．
R, x_i, y_i は実数で小数第 3 位まで表される）
家屋を中心に半径 R の円を書きます。走査線を左から順に移動させて円の左側が接したら、すでに走査線と交わっているものの一覧内の円のなかにその円の中心が入っていないかを調べます。入っていなければ異なる表札をもつ家屋が発見されたことになります。この場合も一覧内の円すべてを調べる必要はなく、じっさいに調べるのはその円よりも Y 座標が大きいものと小さいものそれぞれのなかでその円にもっとも近い円のふたつだけです。
距離を比較するときにそのまま比較しようとすると誤差で Wrong Answer になってしまいます。「任意の 2 つの家屋の距離は R 以下であるか 3R 以上であるかのどちらかである」という条件があるのでやや広めにとって誤差に対応します。
入力されるデータが違うだけでほとんど解法は同じです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
using System; using System.Collections.Generic; using System.Linq; // EventクラスとPairクラスの定義は上記と同じです。 class Program { static double R; static double[] X; static double[] Y; static List<Pair> Outer = new List<Pair>(); // 円 i の中心が円 j の内側にあるか判定する static bool IsInside(int i, int j) { double dx = X[i] - X[j]; double dy = Y[i] - Y[j]; return dx * dx + dy * dy <= R * R * 2; // return dx * dx + dy * dy <= R * R; では誤差で Wrong Answerに //「任意の 2 つの家屋の距離は R 以下であるか 3R 以上であるかのどちらか」なので // * 2 で、かなりガバガバな判定にしています。 } // LowerBoundメソッドも上記と同じです static void Main() { int N; { double[] vs = Console.ReadLine().Split().Select(_ => double.Parse(_)).ToArray(); N = (int)vs[0]; R = vs[1]; } List<Event> events = new List<Event>(); X = new double[N]; Y = new double[N]; for (int i = 0; i < N; i++) { double[] vs = Console.ReadLine().Split().Select(_ => double.Parse(_)).ToArray(); double x = vs[0]; double y = vs[1]; X[i] = x; Y[i] = y; events.Add(new Event(x - R, i, true)); events.Add(new Event(x + R, i, false)); } events = events.OrderBy(_ => _.X).ToList(); List<int> rets = new List<int>(); foreach (Event ev in events) { int id = ev.CircleID; if (ev.IsLeft) { if (Outer.Count() == 0) { rets.Add(ev.CircleID); Pair pair = new Pair(id, Y[id]); Outer.Add(pair); continue; } int index = LowerBound(Y[id]); if (index > 0) { if (IsInside(id, Outer[index - 1].CircleID)) continue; } if (index < Outer.Count) { if (IsInside(id, Outer[index].CircleID)) continue; } rets.Add(ev.CircleID); Pair pair2 = new Pair(id, Y[id]); Outer.Insert(index, pair2); } else { if (Outer.Count > 0) { int index = LowerBound(Y[id]); if (index < Outer.Count && Outer[index].CircleID == id) Outer.RemoveAt(index); } } } Console.WriteLine(rets.Count); } } |
