Круг разрезан несамопересекающейся ломаной, координаты вершин которой заданы парами натуральных чисел - 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();
- }
- }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д