TopCoder SRM 604: FamilyCrest
サンプルが豊富で大きなヒントになっているが、バグ無しの実装が大変な問題。
方針としては、微小距離だけ移動しても自分自身と重ならないような方向が存在するかを判定する。
以下、「移動」というのは微小距離だけ移動という意味で用いている。
２つの線分だけを着目したとき、以下のパターンに分けられる。
- お互い交差も接触もしていない場合
- どの方向に移動しても重ならない
- 「L」 の字、「V」の字のように端点同士が重なっている場合
- 重なっている端点から伸びる線分がなす鋭角の範囲またはその180度逆方向の範囲に移動すれば重ならない。たとえば「L」の字の場合は、(0度, 90度)の範囲、または(180度, 270度)の範囲の方向が移動可能
- 線分が重なっている場合
- 線分と平行にならないように移動すれば重ならない
- 上記以外の「X」の字、「T」の時のように交差している場合
- どの方向に移動しても重なってしまう。
上記から、
(4) のケースがある場合は "Finite"、
(2) のケースがない場合はなんら制限がないため "Infinite"、ある場合は移動可能な角度の範囲を全て調べて共通部分が存在する場合は、"Infinite"、それ以外は "Finite" を返すプログラムを書けばよい。だけどバグ無しで実装するのがかなり大変。
(3) のケースはちゃんと無視するようにしないと (4) のケースとみなされて最後のサンプルが通らなくなる。
public class FamilyCrest { static public void Swap<T>(ref T a, ref T b) { T t = a; a = b; b = t; } static public long DotProduct(PointInt p1, PointInt p2) { return (long)p1.X * p2.X + (long)p1.Y * p2.Y; } static public long CrossProduct(PointInt p1, PointInt p2) { return (long)p1.X * p2.Y - (long)p1.Y * p2.X; } static public int CCW(PointInt p1, PointInt p2, PointInt p3) { p2 -= p1; p3 -= p1; var cross = CrossProduct(p2, p3); if (cross > 0) return +1; if (cross < 0) return -1; if (p2.X * p3.X < 0 || p2.Y * p3.Y < 0) return +2; if (p2.Norm < p3.Norm) return -2; return 0; } static public bool AreIntersect(PointInt p1, PointInt p2, PointInt p3, PointInt p4) { return (CCW(p1, p2, p3) * CCW(p1, p2, p4)) <= 0 && (CCW(p3, p4, p1) * CCW(p3, p4, p2)) <= 0; } bool ShareVertices(PointInt p1, PointInt p2, PointInt q1, PointInt q2) { if (p1 == q1) return true; if (p1 == q2) return true; if (p2 == q1) return true; if (p2 == q2) return true; return false; } struct Range { public double FromArg, ToArg; public bool InRange(double arg) { for (int i = -10; i <= 10; i++) { if (FromArg + Error < arg + i * Math.PI && arg + i * Math.PI < ToArg - Error) return true; } return false; } } const double Error = 1e-9; double Angle(double arg1, double arg2) { var angle = arg2 - arg1; if (angle < -Error) angle += 2 * Math.PI; return angle; } void AddMovableArgRange(List<Range> list, PointInt p1, PointInt p2, PointInt q1, PointInt q2) { if (p2 != q1) return; var arg1 = (p1 - p2).Arg(); var arg2 = (q2 - p2).Arg(); // 鋭角の範囲に移動可能 if (Angle(arg1, arg2) > Math.PI) Swap(ref arg1, ref arg2); if (arg2 < arg1) arg2 += 2 * Math.PI; list.Add( new Range { FromArg = arg1, ToArg = arg2, } ); } bool OnLine(PointInt p1, PointInt p2, PointInt p3) { return CrossProduct(p2 - p1, p3 - p1) == 0; } bool OnLine(PointInt p1, PointInt p2, PointInt p3, PointInt p4) { return OnLine(p1, p2, p3) && OnLine(p2, p3, p4) && OnLine(p1, p3, p4) && OnLine(p1, p2, p4); } public string canBeInfinite(int[] A, int[] B, int[] C, int[] D) { var p1 = new List<PointInt>(); var p2 = new List<PointInt>(); var n = A.Length; for (int i = 0; i < n; i++) { p1.Add(new PointInt(A[i], B[i])); p2.Add(new PointInt(C[i], D[i])); } // 移動可能な方向（角度）の範囲 List<Range> ranges = new List<Range>(); for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (OnLine(p1[i], p2[i], p1[j], p2[j])) continue; if (AreIntersect(p1[i], p2[i], p1[j], p2[j])) { if (ShareVertices(p1[i], p2[i], p1[j], p2[j])) { AddMovableArgRange(ranges, p1[i], p2[i], p1[j], p2[j]); AddMovableArgRange(ranges, p1[i], p2[i], p2[j], p1[j]); AddMovableArgRange(ranges, p2[i], p1[i], p1[j], p2[j]); AddMovableArgRange(ranges, p2[i], p1[i], p2[j], p1[j]); } else { // 端点以外に交点がある場合は、どの方向にも移動できない return "Finite"; } } } } var args = ranges .SelectMany(r => new[] { r.FromArg, r.ToArg }) .SelectMany(a => new[] { a - Math.PI, a, a + Math.PI }) .OrderBy(a => a) .ToArray(); var candidates = args .Zip(args.Skip(1), (a1, a2) => (a1 + a2) / 2.0) .ToArray(); // 制限がないため、どの方向にも移動可能 if (!ranges.Any()) return "Infinite"; foreach (var arg in candidates) { // 制限を全て満たす移動方向が存在した if (ranges.All(r => r.InRange(arg))) { return "Infinite"; } } return "Finite"; } }
