{"id":89,"date":"2018-07-01T11:38:41","date_gmt":"2018-07-01T08:38:41","guid":{"rendered":"http:\/\/dev.content-analysis.ru\/?p=89"},"modified":"2018-07-01T11:49:01","modified_gmt":"2018-07-01T08:49:01","slug":"%d1%81%d0%ba%d0%b0%d0%bd%d0%b8%d1%80%d0%be%d0%b2%d0%b0%d0%bd%d0%b8%d0%b5-%d0%b3%d1%80%d1%8d%d1%85%d0%b5%d0%bc%d0%b0-%d0%bd%d0%b0%d1%85%d0%be%d0%b6%d0%b4%d0%b5%d0%bd%d0%b8%d0%b5-%d0%b2%d1%8b%d0%bf","status":"publish","type":"post","link":"http:\/\/dev.content-analysis.ru\/?p=89","title":{"rendered":"\u0421\u043a\u0430\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0413\u0440\u044d\u0445\u0435\u043c\u0430 &#8212; \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \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"},"content":{"rendered":"<p style=\"padding-left: 30px;\">\u0415\u0449\u0435 \u043e\u0434\u0438\u043d \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044e \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. \u0422\u0435\u043f\u0435\u0440\u044c \u0443\u0436\u0435 \u043d\u0435 \u0442\u0430\u043a\u043e\u0439 \u0442\u043e\u0440\u043c\u043e\u0437\u043d\u043e\u0439 (\u043d\u0435 O=n^3, \u0430 O=n log n ) &#8212; \u0421\u043a\u0430\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0413\u0440\u044d\u0445\u0435\u043c\u0430.<\/p>\n<pre class=\"brush: csharp; title: ; notranslate\" title=\"\">\r\n\r\n&lt;\/pre&gt;\r\n\/\/\/ &lt;summary&gt;\r\n\/\/\/ \u0421\u043a\u0430\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0413\u0440\u044d\u0445\u0435\u043c\u0430.\r\n\/\/\/ &lt;\/summary&gt;\r\n\/\/\/ &lt;param name=&quot;set&quot;&gt;&lt;\/param&gt;\r\n\/\/\/ &lt;returns&gt;&lt;\/returns&gt;\r\npublic static IEnumerable&lt;Point&gt; ConvexHull(Point[] points)\r\n{\r\nvar upper = new List&lt;Point&gt;();\r\nvar lower = new List&lt;Point&gt;();\r\n\r\n\/\/\u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u0442\u043e\u0447\u043a\u0438 P \u0438 Q \u0432 \u043b\u0435\u043a\u0441\u0438\u043a\u043e\u0433\u0440\u0430\u0444\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435: \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u043f\u043e x,\r\n\/\/\u0438 \u0435\u0441\u043b\u0438 \u0443 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 \u0442\u043e\u0447\u0435\u043a Px = Qx, \u0442\u043e \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u0438\u0445 \u0442\u0430\u043a\u0436\u0435 \u043f\u043e y\r\npoints = points.OrderBy(p =&gt; p.X).ThenBy(p =&gt; p.Y).ToArray();\r\n\r\nupper.AddRange(points.Take(2));\r\n\/\/\u0435\u0441\u043b\u0438 \u0432 upper \u0431\u043e\u043b\u044c\u0448\u0435 \u0434\u0432\u0443\u0445 \u0442\u043e\u0447\u0435\u043a \u0438 \u0435\u0441\u043b\u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0435 \u0442\u0440\u0438 \u0442\u043e\u0447\u043a\u0438 upper \u043d\u0435\r\n\/\/\u043e\u0431\u0440\u0430\u0437\u0443\u044e\u0442 \u043f\u043e\u0432\u043e\u0440\u043e\u0442 \u043d\u0430\u043f\u0440\u0430\u0432\u043e, \u0442\u043e \u0443\u0434\u0430\u043b\u044f\u0435\u043c \u0441\u0440\u0435\u0434\u043d\u044e\u044e \u0438\u0437 \u043d\u0438\u0445\r\nfor (int i = 2; i &lt; points.Count(); i++)\r\n{\r\nupper.Add(points[i]);\r\nwhile (upper.Count() &gt; 2 &amp;&amp; !IsRightTurn(upper.ElementAt(upper.Count - 1),\r\nupper.ElementAt(upper.Count - 2), upper.ElementAt(upper.Count - 3)))\r\n{\r\nupper.RemoveAt(upper.Count() - 2);\r\n}\r\n}\r\n\r\nlower.Add(points.ElementAt(points.Count() - 1));\r\nlower.Add(points.ElementAt(points.Count() - 2));\r\n\/\/\u0435\u0441\u043b\u0438 \u0432 lower \u0431\u043e\u043b\u044c\u0448\u0435 \u0434\u0432\u0443\u0445 \u0442\u043e\u0447\u0435\u043a \u0438 \u0435\u0441\u043b\u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0435 \u0442\u0440\u0438 \u0442\u043e\u0447\u043a\u0438 lower \u043d\u0435\r\n\/\/\u043e\u0431\u0440\u0430\u0437\u0443\u044e\u0442 \u043f\u043e\u0432\u043e\u0440\u043e\u0442 \u043d\u0430\u043f\u0440\u0430\u0432\u043e, \u0442\u043e \u0443\u0434\u0430\u043b\u044f\u0435\u043c \u0441\u0440\u0435\u0434\u043d\u044e\u044e \u0438\u0437 \u043d\u0438\u0445\r\nfor (int i = points.Count() - 2; i &gt;= 0; i--)\r\n{\r\nlower.Add(points.ElementAt(points.Count() - 1));\r\nwhile (lower.Count() &gt; 2 &amp;&amp; !IsRightTurn(lower.ElementAt(lower.Count - 1),\r\nlower.ElementAt(lower.Count - 2), lower.ElementAt(lower.Count - 3)))\r\n{\r\nlower.RemoveAt(lower.Count() - 2);\r\n}\r\n}\r\n\r\n\/\/\u0443\u0434\u0430\u043b\u044f\u0435\u043c \u043f\u0435\u0440\u0432\u0443\u044e \u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u044e\u044e \u0442\u043e\u0447\u043a\u0438 \u0432 lower, \u0447\u0442\u043e\u0431\u044b \u0438\u0437\u0431\u0435\u0436\u0430\u0442\u044c \u0434\u0443\u0431\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0441 upper\r\nlower.RemoveAt(lower.Count() - 1);\r\nlower.RemoveAt(0);\r\n\r\nreturn upper.Concat(lower);\r\n}\r\n&lt;pre&gt;\r\n\r\n<\/pre>\n<p>\u0412\u043d\u0430\u0447\u0430\u043b\u0435 \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u043f\u043e X. \u041d\u0430 \u0441\u043b\u0443\u0447\u0430\u0439, \u0435\u0441\u043b\u0438 \u0432\u0434\u0440\u0443\u0433 \u0431\u0443\u0434\u0435\u0442 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0442\u043e\u0447\u0435\u043a \u0441 \u043e\u0434\u043d\u0438\u043c X, \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u0438\u0445 \u043b\u0435\u043a\u0441\u0438\u043a\u043e\u0433\u0440\u0430\u0444\u0438\u0447\u0435\u0441\u043a\u0438 &#8212; \u0442\u0430\u043a\u0436\u0435 \u0438 \u043f\u043e Y.<\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u043f\u0435\u0440\u0432\u044b\u0435 \u0434\u0432\u0435 \u0442\u043e\u0447\u043a\u0438 \u0432 \u0441\u043f\u0438\u0441\u043e\u043a upper (\u0432\u0435\u0440\u0445\u043d\u044f\u044f \u0447\u0430\u0441\u0442\u044c \u0432\u044b\u043f\u0443\u043a\u043b\u043e\u0439 \u043e\u0431\u043e\u043b\u043e\u0447\u043a\u0438) \u0438 \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u043c \u043e\u0431\u0445\u043e\u0434 \u0432\u0441\u0435\u0445 \u0442\u043e\u0447\u043a\u0443 \u0432 \u0446\u0438\u043a\u043b\u0435 for. \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0442\u0440\u0435\u0442\u044c\u044e \u0438 \u0434\u0430\u043b\u0435\u0435 \u0432 \u0446\u0438\u043a\u043b\u0435 while \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u043c \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0443 &#8212; \u0435\u0441\u0442\u044c \u043b\u0438 \u0432 upper \u043a\u0430\u043a \u043c\u0438\u043d\u0438\u043c\u0443\u043c 3 \u0442\u043e\u0447\u043a\u0438 \u0438 \u043e\u0431\u0440\u0430\u0437\u0443\u044e\u0442 \u043b\u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0435 \u0442\u0440\u0438 \u043f\u043e\u0432\u043e\u0440\u043e\u0442 \u043d\u0430\u043f\u0440\u0430\u0432\u043e. \u0415\u0441\u043b\u0438 \u0442\u0440\u0438 \u0442\u043e\u0447\u043a\u0438 \u0435\u0441\u0442\u044c, \u043d\u043e \u043f\u043e\u0432\u043e\u0440\u043e\u0442\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e \u043d\u0435 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 &#8212; \u0443\u0434\u0430\u043b\u044f\u0435\u043c \u0441\u0440\u0435\u0434\u043d\u044e\u044e \u0438\u0437 \u044d\u0442\u0438\u0445 \u0442\u0440\u0435\u0445 \u0438 \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0435\u043c \u0440\u0430\u0431\u043e\u0442\u0443 while.<\/p>\n<p>\u0410\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u044b\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043f\u043e\u0441\u0442\u0443\u043f\u0430\u0435\u043c \u0441 &#171;\u043d\u0438\u0436\u043d\u0435\u0439&#187; \u0447\u0430\u0441\u0442\u044c\u044e \u0432\u044b\u043f\u0443\u043a\u043b\u043e\u0439 \u043e\u0431\u043e\u043b\u043e\u0447\u043a\u0438 &#8212; \u0441\u043f\u0438\u0441\u043e\u043a lower.<\/p>\n<p>\u0427\u0442\u043e\u0431\u044b \u0438\u0437\u0431\u0435\u0436\u0430\u0442\u044c \u0434\u0443\u0431\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0442\u043e\u0447\u0435\u043a \u0432 lower \u0438 upper, \u0432 lower \u0443\u0434\u0430\u043b\u044f\u0435\u043c \u043f\u0435\u0440\u0432\u0443\u044e \u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u044e\u044e \u0442\u043e\u0447\u043a\u0438.<\/p>\n<p>\u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c upper \u0441 \u043f\u0440\u0438\u0441\u043e\u0435\u0434\u0438\u043d\u0435\u043d\u043d\u044b\u043c \u043a \u043d\u0435\u043c\u0443 \u0432 \u043a\u043e\u043d\u0435\u0446 lower.<\/p>\n<p>&nbsp;<\/p>\n<p>\u041f\u043e\u0432\u043e\u0440\u043e\u0442 \u043d\u0430\u043f\u0440\u0430\u0432\u043e \u043c\u043e\u0436\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u043f\u043e \u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u044e \u0442\u0440\u0435\u0442\u044c\u0435\u0439 \u0442\u043e\u0447\u043a\u0438 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043e\u0442\u0440\u0435\u0437\u043a\u0430, \u043e\u0431\u0440\u0430\u0437\u0443\u0435\u043c\u043e\u0433\u043e \u043f\u0435\u0440\u0432\u043e\u0439 \u0438 \u0432\u0442\u043e\u0440\u043e\u0439 \u0442\u043e\u0447\u043a\u043e\u0439:<\/p>\n<pre class=\"brush: csharp; title: ; notranslate\" title=\"\">\r\n\r\n\/\/\/ &lt;summary&gt;\r\n\/\/\/ \u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u043b\u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0442\u0440\u0435\u0445 \u0442\u043e\u0447\u0435\u043a \u043f\u043e\u0432\u0442\u043e\u0440\u043e\u0442 \u043d\u0430\u043f\u0440\u0430\u0432\u043e.\r\n\/\/\/ &lt;\/summary&gt;\r\n\/\/\/ &lt;param name=&quot;a&quot;&gt;&lt;\/param&gt;\r\n\/\/\/ &lt;param name=&quot;b&quot;&gt;&lt;\/param&gt;\r\n\/\/\/ &lt;param name=&quot;c&quot;&gt;&lt;\/param&gt;\r\n\/\/\/ &lt;returns&gt;&lt;\/returns&gt;\r\npublic static bool IsRightTurn(Point a, Point b, Point c)\r\n{\r\nvar seg = new LineSegment(a, b);\r\nreturn WherePoint(seg, c) &lt; 0;\r\n}\r\n\r\n\/\/\/ &lt;summary&gt;\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\/\/\/ &lt;\/summary&gt;\r\n\/\/\/ &lt;returns&gt;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&lt;\/returns&gt;\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<\/pre>\n<p>\u041d\u0438\u0436\u0435 \u043a\u043b\u0430\u0441\u0441\u044b \u0442\u043e\u0447\u043a\u0438 \u0438 \u043e\u0442\u0440\u0435\u0437\u043a\u0430, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u043e\u0433\u043e \u0432 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435:<\/p>\n<pre class=\"brush: csharp; title: ; notranslate\" title=\"\">\r\n\r\n&lt;\/pre&gt;\r\n\/\/\/ &lt;summary&gt;\r\n\/\/\/ \u041d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0439 \u043e\u0442\u0440\u0435\u0437\u043e\u043a (p -&gt; q). \u0412 \u043e\u0431\u0449\u0435\u043c \u044d\u0442\u043e \u0432\u0435\u043a\u0442\u043e\u0440.\r\n\/\/\/ &lt;\/summary&gt;\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\npublic class PointNamed\r\n{\r\npublic int X { get; set; }\r\npublic int Y { get; set; }\r\npublic string Name { get; set; }\r\npublic Point Point;\r\n\r\npublic PointNamed(string name, Point point)\r\n{\r\nthis.Name = name;\r\nthis.X = point.X;\r\nthis.Y = point.Y;\r\nthis.Point = point;\r\n}\r\n}\r\n&lt;pre&gt;\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u0415\u0449\u0435 \u043e\u0434\u0438\u043d \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044e \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. \u0422\u0435\u043f\u0435\u0440\u044c \u0443\u0436\u0435 \u043d\u0435 \u0442\u0430\u043a\u043e\u0439 \u0442\u043e\u0440\u043c\u043e\u0437\u043d\u043e\u0439 (\u043d\u0435 O=n^3, \u0430 O=n log n ) &#8212; \u0421\u043a\u0430\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0413\u0440\u044d\u0445\u0435\u043c\u0430. \u0412\u043d\u0430\u0447\u0430\u043b\u0435 \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u043f\u043e X. \u041d\u0430 \u0441\u043b\u0443\u0447\u0430\u0439, \u0435\u0441\u043b\u0438 \u0432\u0434\u0440\u0443\u0433 \u0431\u0443\u0434\u0435\u0442 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0442\u043e\u0447\u0435\u043a \u0441 \u043e\u0434\u043d\u0438\u043c X, &hellip; <a href=\"http:\/\/dev.content-analysis.ru\/?p=89\">\u0427\u0438\u0442\u0430\u0442\u044c \u0434\u0430\u043b\u0435\u0435 <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[3,11],"class_list":["post-89","post","type-post","status-publish","format-standard","hentry","category-1","tag-c","tag-11"],"_links":{"self":[{"href":"http:\/\/dev.content-analysis.ru\/index.php?rest_route=\/wp\/v2\/posts\/89","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/dev.content-analysis.ru\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/dev.content-analysis.ru\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/dev.content-analysis.ru\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/dev.content-analysis.ru\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=89"}],"version-history":[{"count":4,"href":"http:\/\/dev.content-analysis.ru\/index.php?rest_route=\/wp\/v2\/posts\/89\/revisions"}],"predecessor-version":[{"id":93,"href":"http:\/\/dev.content-analysis.ru\/index.php?rest_route=\/wp\/v2\/posts\/89\/revisions\/93"}],"wp:attachment":[{"href":"http:\/\/dev.content-analysis.ru\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=89"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/dev.content-analysis.ru\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=89"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/dev.content-analysis.ru\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=89"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}