\u0414\u0430\u0432\u043d\u043e \u0445\u043e\u0442\u0435\u043b \u043d\u0430\u0447\u0430\u0442\u044c \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0438 \u0438 \u0432\u043e\u0442 \u043d\u0430\u0447\u0430\u043b.<\/p>\n
\u042d\u0442\u043e, \u0441\u0430\u043c\u044b\u0439 \u043f\u0435\u0440\u0432\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438\u0437 \u043a\u043d\u0438\u0433\u0438 «\u0412\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u044f. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0438 \u043f\u0440\u0438\u043b\u043e\u0436\u0435\u043d\u0438\u044f».\u00a0 \u0412 \u043a\u043d\u0438\u0433\u0435 \u043e\u043d \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f SlowConvexHull. \u0420\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043e\u043d \u043d\u0435\u0438\u0434\u0435\u0430\u043b\u044c\u043d\u043e — \u0438\u0437-\u0437\u0430 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u0432 \u043d\u0435\u043c \u043d\u0435\u0442 \u0440\u0430\u0437\u043d\u0438\u0446\u044b \u0432 \u0442\u043e\u043c, \u0433\u0434\u0435 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0442\u043e\u0447\u043a\u0430 — \u043d\u0430\/\u043f\u0435\u0440\u0435\u0434\/\u043f\u043e\u0437\u0430\u0434\u0438 \u043e\u0442\u0440\u0435\u0437\u043a\u0430. \u0425\u043e\u0442\u044f \u044d\u0442\u043e \u043d\u0435 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u0430 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u043c\u043e\u0435\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438.<\/p>\n
\u041f\u0438\u0441\u0430\u043b \u0435\u0433\u043e \u043d\u0430 C#. \u0414\u0443\u043c\u0430\u044e, \u043d\u0430\u0434\u043e \u0431\u044b \u043f\u043e\u043d\u0435\u043c\u043d\u043e\u0433\u0443 \u043d\u0430\u0447\u0438\u043d\u0430\u0442\u044c \u043e\u0441\u0432\u0430\u0438\u0432\u0430\u0442\u044c \u0447\u0442\u043e-\u0442\u043e \u043d\u0430 Python \u0434\u043b\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0432\u0440\u043e\u0434\u0435 \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0442\u043e\u0447\u043a\u0438 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043e\u0442\u0440\u0435\u0437\u043a\u0430. \u0412\u043d\u0430\u0447\u0430\u043b\u0435 \u043c\u0435\u043d\u044f \u044d\u0442\u0430 \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u043a\u0430 \u043e\u0447\u0435\u043d\u044c \u0441\u043c\u0443\u0442\u0438\u043b\u0430, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043d\u0435 \u043f\u043e\u0434\u0443\u043c\u0430\u043b, \u0447\u0442\u043e \u0443 \u044d\u0442\u043e\u0433\u043e \u043e\u0442\u0440\u0435\u0437\u043a\u0430 \u0435\u0441\u0442\u044c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0435. \u0412\u0435\u0440\u043e\u044f\u0442\u043d\u043e, \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0435\u0449\u0435 \u043e\u0447\u0435\u043d\u044c \u043c\u043d\u043e\u0433\u043e \u0438 \u043d\u0435 \u0443\u0432\u0435\u0440\u0435\u043d, \u0441\u0442\u043e\u0438\u0442 \u043b\u0438 \u0432\u0441\u0435 \u0438\u0445 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u044b\u0432\u0430\u0442\u044c \u0441\u0430\u043c\u043e\u0441\u0442\u043e\u044f\u0442\u0435\u043b\u044c\u043d\u043e \u043f\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0430\u043c.<\/p>\n
\u041a\u043e\u0434 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u043a\u0438 \u0434\u043b\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430.<\/p>\n
\u041a\u043b\u0430\u0441\u0441 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u043e\u0442\u0440\u0435\u0437\u043a\u0430<\/p>\n
\r\n\r\n\/\/\/ <summary>\r\n\/\/\/ \u041d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0439 \u043e\u0442\u0440\u0435\u0437\u043e\u043a (p -> q).\r\n\/\/\/ <\/summary>\r\npublic class LineSegment\r\n{\r\npublic Point P { get; private set; }\r\npublic Point Q { get; private set; }\r\n\r\npublic LineSegment(Point p, Point q)\r\n{\r\nthis.P = p;\r\nthis.Q = q;\r\n}\r\n}\r\n\r\n<\/pre>\n\u0421\u0430\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c:<\/p>\n
\r\n\r\n\/\/\/ <summary>\r\n\/\/\/ \u041f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u0435 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0432\u044b\u043f\u0443\u043a\u043b\u043e\u0439 \u043e\u0431\u043e\u043b\u043e\u0447\u043a\u0438 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0442\u043e\u0447\u0435\u043a.\r\n\/\/\/ <\/summary>\r\n\/\/\/ <param name="set"><\/param>\r\n\/\/\/ <returns><\/returns>\r\npublic static List<Point> SlowConvexHull(IEnumerable<Point> set)\r\n{\r\n\/\/\u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u0432\u0435\u043a\u0442\u043e\u0440\u044b \u0434\u043b\u044f \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0442\u043e\u0447\u0435\u043a\r\nvar vectors = GetAllLineSegmentsForPointsSet(set.ToArray());\r\n\/\/\u0432\u0435\u043a\u0442\u043e\u0440\u0430, \u0432\u0445\u043e\u0434\u044f\u0449\u0438\u0435 \u0432 \u0432\u044b\u043f\u0443\u043a\u043b\u0443\u044e \u043e\u0431\u043e\u043b\u043e\u0447\u043a\u0443\r\nList<LineSegment> E = new List<LineSegment>();\r\n\r\n\/\/\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u0435 \u0432\u0435\u043a\u0442\u043e\u0440\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0447\u0430\u0441\u0442\u044c\u044e \u0432\u044b\u043f\u0443\u043a\u043b\u043e\u0439 \u043e\u0431\u043e\u043b\u043e\u0447\u043a\u0438.\r\nbool valid;\r\nforeach(var ve in vectors)\r\n{\r\nvalid = true;\r\n\/\/\u0442\u043e\u0447\u043a\u0438, \u043d\u0435 \u044f\u0432\u043b\u044f\u044e\u0449\u0438\u0435\u0441\u044f \u0447\u0430\u0441\u0442\u044c\u044e \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u0432\u0435\u043a\u0442\u043e\u0440\u0430 ve\r\nvar points = set.Where(a => (a.X != ve.P.X && a.Y != ve.P.Y) || (a.X != ve.Q.X && a.Y != ve.Q.Y));\r\n\r\nforeach (var p in points)\r\n{\r\nif (WherePoint(ve, p) > 0)\r\n{\r\nvalid = false;\r\nbreak;\r\n}\r\n}\r\n\r\nif (valid)\r\nE.Add(ve);\r\n}\r\n\r\n\/\/\u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u044b\u0435 \u0432\u0435\u043a\u0442\u043e\u0440\u0430\r\nE = E.GroupBy(a => new { a.P, a.Q }).Select(a => a.First()).ToList();\r\n\r\n\/\/\u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u043f\u043e\u043b\u0438\u0433\u043e\u043d\u0430, \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u0432 \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u0434\u0432\u0438\u0436\u0435\u043d\u0438\u044f\r\n\/\/\u043f\u043e \u043e\u0431\u043e\u043b\u043e\u0447\u043a\u0435 \u043f\u043e \u0447\u0430\u0441\u043e\u0432\u043e\u0439 \u0441\u0442\u0440\u0435\u043b\u043a\u0435\r\nvar res = OrderLineSegments(E);\r\nreturn res;\r\n}\r\n\r\n\/\/\/ <summary>\r\n\/\/\/ \u041e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442, \u0433\u0434\u0435 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0442\u043e\u0447\u043a\u0430 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0432\u0435\u043a\u0442\u043e\u0440\u0430.\r\n\/\/\/ (bx-ax)*(py-ay)-(by-ay)*(px-ax)\r\n\/\/\/ <\/summary>\r\n\/\/\/ <returns>i. i \u0431\u043e\u043b\u044c\u0448\u0435 0, \u0435\u0441\u043b\u0438 \u0442\u043e\u0447\u043a\u0430 \u0441\u043b\u0435\u0432\u0430 \u043e\u0442 \u0432\u0435\u043a\u0442\u043e\u0440\u0430,\r\n\/\/\/ a \u043c\u0435\u043d\u044c\u0448\u0435 0, \u0435\u0441\u043b\u0438 \u0442\u043e\u0447\u043a\u0430 \u0441\u043f\u0440\u0430\u0432\u0430 \u043e\u0442 \u0432\u0435\u043a\u0442\u043e\u0440\u0430\r\n\/\/\/ \u0438 = 0, \u0435\u0441\u043b\u0438 \u0442\u043e\u0447\u043a\u0430 \u043d\u0430 \u0432\u0435\u043a\u0442\u043e\u0440\u0435, \u043f\u0440\u044f\u043c\u043e \u043f\u043e \u0432\u0435\u043a\u0442\u043e\u0440\u0443 \u0438\u043b\u0438 \u0441\u0437\u0430\u0434\u0438 \u0432\u0435\u043a\u0442\u043e\u0440\u0430<\/returns>\r\npublic static int WherePoint(LineSegment vector, Point p)\r\n{\r\nreturn (vector.Q.X - vector.P.X) * (p.Y - vector.P.Y)\r\n- (vector.Q.Y - vector.P.Y) * (p.X - vector.P.X);\r\n}\r\n\r\n\/\/\/ <summary>\r\n\/\/\/ \u041f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u0435 \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u043e\u0433\u043e \u0432 \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u043e\u0431\u0445\u043e\u0434\u0430 \u043f\u043e \u0447\u0430\u0441\u043e\u0432\u043e\u0439 \u0441\u0442\u0440\u0435\u043b\u043a\u0435\r\n\/\/\/ \u0441\u043f\u0438\u0441\u043a\u0430 \u0432\u0435\u0440\u0448\u0438\u043d \u0432\u044b\u043f\u0443\u043a\u043b\u043e\u0439 \u043e\u0431\u043e\u043b\u043e\u0447\u043a\u0438 \u0438\u0437 \u0441\u043f\u0438\u0441\u043a\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0445 \u043e\u0442\u0440\u0435\u0437\u043a\u043e\u0432.\r\n\/\/\/ <\/summary>\r\n\/\/\/ <returns><\/returns>\r\npublic static List<Point> OrderLineSegments(List<LineSegment> vectors)\r\n{\r\nList<Point> L = new List<Point>();\r\n\r\nvar fst = vectors.First();\r\nL.Add(fst.P);\r\nL.Add(fst.Q);\r\n\r\nwhile (true)\r\n{\r\nvar po = vectors.Where(v => v.P.X == L.Last().X && v.P.Y == L.Last().Y).First().Q;\r\nL.Add(po);\r\nif (L.First().X == po.X && L.First().Y == po.Y)\r\nbreak;\r\n}\r\n\r\nreturn L;\r\n}\r\n\r\n\/\/\/ <summary>\r\n\/\/\/ \u041f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u0435 \u0432\u0441\u0435\u0445 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0432\u0435\u043a\u0442\u043e\u0440\u043e\u0432 \u0434\u043b\u044f \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0442\u043e\u0447\u0435\u043a.\r\n\/\/\/ <\/summary>\r\n\/\/\/ <param name="points"><\/param>\r\n\/\/\/ <returns><\/returns>\r\npublic static List<LineSegment> GetAllLineSegmentsForPointsSet(Point[] points)\r\n{\r\nList<LineSegment> res = new List<LineSegment>();\r\n\r\nfor (int i = 0; i < points.Length; i++)\r\n{\r\nfor (int j = 0; j < points.Length; j++)\r\n{\r\nif(i != j)\r\n{\r\nres.Add(new LineSegment(points[i], points[j]));\r\nres.Add(new LineSegment(points[j], points[i]));\r\n}\r\n}\r\n}\r\n\r\nres = res.GroupBy(x => new { x.P, x.Q }).Select(x => x.First()).ToList<LineSegment>();\r\nreturn res;\r\n}\r\n\r\n<\/pre>\n\u0412\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430:<\/p>\n
\r\n\r\npublic static void Main(string[] args)\r\n{\r\n\/\/\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a \u043d\u0430 \u043f\u043b\u043e\u0441\u043a\u043e\u0441\u0442\u0438\r\nList<Point> P = GetRandomPoints(5, maxXY: 10);\r\n\r\n\/\/\u0442\u0435\u0441\u0442:\r\nP = GetRandomPointsTest();\r\n\r\n\/\/\u0432\u0435\u0440\u0448\u0438\u043d\u044b \u043e\u0431\u043e\u043b\u043e\u0447\u043a\u0438 \u0432\u044b\u043f\u0443\u043a\u043b\u043e\u0439 \u043f\u043b\u043e\u0441\u043a\u043e\u0441\u0442\u0438 CH(P) \u0432 \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u043e\u0431\u0445\u043e\u0434\u0430 \u043f\u043e \u0447\u0430\u0441\u043e\u0432\u043e\u0439 \u0441\u0442\u0440\u0435\u043b\u043a\u0435\r\nIEnumerable<Point> L = SlowConvexHull(P);\r\n\/\/\u0440\u0438\u0441\u0443\u0435\u043c \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u0438 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u0443\u044e \u0432\u044b\u043f\u0443\u043a\u043b\u0443\u044e \u043e\u0431\u043e\u043b\u043e\u0447\u043a\u0443 \u0434\u043b\u044f \u043d\u0438\u0445\r\nDrawPointsSetWithConvexHull(P, L);\r\n\r\nforeach(var po in L)\r\nConsole.WriteLine(string.Format("X: {0} and Y: {1}", po.X, po.Y));\r\nConsole.ReadLine();\r\n}\r\n\r\n\/\/\/ <summary>\r\n\/\/\/ \u041f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u0442\u043e\u0447\u0435\u043a.\r\n\/\/\/ <\/summary>\r\n\/\/\/ <param name="num">\u0432\u0435\u0440\u043d\u0443\u0442\u044c \u044d\u0442\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0442\u043e\u0447\u0435\u043a<\/param>\r\n\/\/\/ <param name="maxXY">\u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u0434\u043b\u0438\u043d\u0430 \u043f\u043e \u0430\u0431\u0441\u0446\u0438\u0441\u0441\u0435 \u0438 \u043e\u0440\u0434\u0438\u043d\u0430\u0442\u0435\r\n\/\/\/ (\u043e\u0442\u0441\u0447\u0435\u0442 \u043e\u0442 0, \u0431\u0435\u0437 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439)<\/param>\r\n\/\/\/ <returns><\/returns>\r\npublic static List<Point> GetRandomPoints(int num, int maxXY = 25)\r\n{\r\nList<Point> res = new List<Point>();\r\nRandom r = new Random();\r\nint x;\r\nint y;\r\n\r\nfor(int i = 0; i < num; i++)\r\n{\r\nx = r.Next(maxXY + 1);\r\ny = r.Next(maxXY + 1);\r\nres.Add(new Point(x, y));\r\n}\r\n\r\nres =\r\nres.GroupBy(a => new { a.X, a.Y })\r\n.Select(a => a.First())\r\n.ToList();\r\n\r\nreturn res;\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"\u0414\u0430\u0432\u043d\u043e \u0445\u043e\u0442\u0435\u043b \u043d\u0430\u0447\u0430\u0442\u044c \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0438 \u0438 \u0432\u043e\u0442 \u043d\u0430\u0447\u0430\u043b. \u042d\u0442\u043e, \u0441\u0430\u043c\u044b\u0439 \u043f\u0435\u0440\u0432\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438\u0437 \u043a\u043d\u0438\u0433\u0438 «\u0412\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u044f. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0438 \u043f\u0440\u0438\u043b\u043e\u0436\u0435\u043d\u0438\u044f».\u00a0 \u0412 \u043a\u043d\u0438\u0433\u0435 \u043e\u043d \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f SlowConvexHull. \u0420\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043e\u043d \u043d\u0435\u0438\u0434\u0435\u0430\u043b\u044c\u043d\u043e — \u0438\u0437-\u0437\u0430 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u0432 \u043d\u0435\u043c \u043d\u0435\u0442 \u0440\u0430\u0437\u043d\u0438\u0446\u044b \u0432 \u0442\u043e\u043c, \u0433\u0434\u0435 … \u0427\u0438\u0442\u0430\u0442\u044c \u0434\u0430\u043b\u0435\u0435