minimum perimeter
| 771 | } |
| 772 | // minimum perimeter |
| 773 | double minimum_enclosing_rectangle(vector<PT> &p) { |
| 774 | int n = p.size(); |
| 775 | if (n <= 2) return perimeter(p); |
| 776 | int mndot = 0; double tmp = dot(p[1] - p[0], p[0]); |
| 777 | for (int i = 1; i < n; i++) { |
| 778 | if (dot(p[1] - p[0], p[i]) <= tmp) { |
| 779 | tmp = dot(p[1] - p[0], p[i]); |
| 780 | mndot = i; |
| 781 | } |
| 782 | } |
| 783 | double ans = inf; |
| 784 | int i = 0, j = 1, mxdot = 1; |
| 785 | while (i < n) { |
| 786 | PT cur = p[(i + 1) % n] - p[i]; |
| 787 | while (cross(cur, p[(j + 1) % n] - p[j]) >= 0) j = (j + 1) % n; |
| 788 | while (dot(p[(mxdot + 1) % n], cur) >= dot(p[mxdot], cur)) mxdot = (mxdot + 1) % n; |
| 789 | while (dot(p[(mndot + 1) % n], cur) <= dot(p[mndot], cur)) mndot = (mndot + 1) % n; |
| 790 | ans = min(ans, 2.0 * ((dot(p[mxdot], cur) / cur.norm() - dot(p[mndot], cur) / cur.norm()) + dist_from_point_to_line(p[i], p[(i + 1) % n], p[j]))); |
| 791 | i++; |
| 792 | } |
| 793 | return ans; |
| 794 | } |
| 795 | // given n points, find the minimum enclosing circle of the points |
| 796 | // call convex_hull() before this for faster solution |
| 797 | // expected O(n) |