Круг разрезан несамопересекающейся ломаной, координаты вершин которой заданы парами натуральных чисел - C#
Формулировка задачи:
Круг разрезан несамопересекающейся ломаной, координаты вершин которой заданы парами натуральных чисел (x1,y1), ..., (xk,yk). Первая и последняя вершины лежат на границе круга, а остальные внутри его. Определить, можно ли разъединить две получившиеся части круга (выход из плоскости и повороты разнимаемых частей не допускается).
Решение задачи: «Круг разрезан несамопересекающейся ломаной, координаты вершин которой заданы парами натуральных чисел»
textual
Листинг программы
struct Point { public double X; public double Y; public Point(double x, double y) { X = x; Y = y; } public Point(Point from, Point to) { X = to.X - from.X; Y = to.Y - from.Y; } // [0; 2pi] public double GetAngle() { var angle = Math.Atan2(Y, X); if (angle < 0) { return Math.PI * 2 + angle; } return angle; } public override string ToString() { return $"({X}, {Y})"; } } static class AngleHelper { private static Point[] ToSegments(double fromAngle, double toAngle) { if (fromAngle > toAngle) { return new[] { new Point(fromAngle, Math.PI * 2), new Point(0, toAngle) }; } return new[] { new Point(fromAngle, toAngle) }; } private static Point? IntersectSegments(Point first, Point second) { double from = Math.Max(first.X, second.X); double to = Math.Min(first.Y, second.Y); return to < from - 1e-8 ? (Point?)null : new Point(Math.Min(from, to), Math.Max(from, to)); } private static Point GetAngle(Point first, Point center, Point last) { var firstOffset = new Point(center, first); var lastOffset = new Point(center, last); var fromAngle = firstOffset.GetAngle(); var toAngle = lastOffset.GetAngle(); return new Point(fromAngle, toAngle); } private static Point GetStraightAngle(Point center, Point last) { var offset = new Point(center, last); var toAngle = offset.GetAngle(); return new Point((toAngle + Math.PI) % (Math.PI * 2), toAngle); } public static IList<Point> IntersectAngles(Point firstAngle, Point secondAngle) { Point[] firstSegments = ToSegments(firstAngle.X, firstAngle.Y); Point[] secondSegments = ToSegments(secondAngle.X, secondAngle.Y); var resultAngles = new List<Point>(); foreach (var firstSegment in firstSegments) { foreach (var secondSegment in secondSegments) { Point? intersected = IntersectSegments(firstSegment, secondSegment); if (intersected != null) { resultAngles.Add((Point)intersected); } } } return resultAngles; } public static IEnumerable<Point> GetAngles(IList<Point> polygonalLine) { yield return GetStraightAngle(polygonalLine[0], polygonalLine[1]); for (int i = 1; i < polygonalLine.Count - 1; i++) { yield return GetAngle(polygonalLine[i - 1], polygonalLine[i], polygonalLine[i + 1]); } var last = GetStraightAngle(polygonalLine[polygonalLine.Count - 1], polygonalLine[polygonalLine.Count - 2]); yield return new Point(last.Y, last.X); } public static double GetTotalAngleValue(Point angle) { double value = angle.Y - angle.X; if (value < 0) { value += Math.PI * 2; } return value; } } static class SeveringResolver { public static IList<Point> GetDirectionsToSever(IList<Point> polygonalLine) { var intersection = new List<Point>(); intersection.Add(new Point(0, Math.PI * 2)); foreach (Point angle in AngleHelper.GetAngles(polygonalLine).OrderBy(AngleHelper.GetTotalAngleValue)) { var newIntersection = new List<Point>(); foreach (Point oldAngle in intersection) { newIntersection.AddRange(AngleHelper.IntersectAngles(oldAngle, angle)); } intersection = newIntersection; } return intersection; } } void Main() { Point[] polygonalLine = { new Point(0, 0), new Point(0, 2), new Point(1, 1), new Point(1, 3), new Point(0, 4) }; var severingAngles = SeveringResolver.GetDirectionsToSever(polygonalLine); foreach (var angle in severingAngles) { var fromDegree = angle.X * 360 / 2 / Math.PI; var toDegree = angle.Y * 360 / 2 / Math.PI; new Point(fromDegree, toDegree).Dump(); } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д