1 /**************************************************************  2     Problem: 1185  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:180 ms  7     Memory:2372 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <cmath> 12 #include <algorithm> 13   14 #define P Point 15 using namespace std; 16 typedef double lf; 17 const int N = 50005; 18 const lf eps = 1e-8; 19   20 struct Point { 21     lf x, y; 22     P() {} 23     P(lf _x, lf _y) : x(_x), y(_y) {} 24       25     inline bool operator < (const P &X) const { 26         return fabs(y - X.y) < eps ? x < X.x : y < X.y; 27     } 28     inline bool operator == (const P &X) const { 29         return fabs(x - X.x) < eps && fabs(y - X.y) < eps; 30     } 31     inline bool operator != (const P &X) const { 32         return !(*this == X); 33     } 34     inline P operator + (const P &X) const { 35         return P(x + X.x, y + X.y); 36     } 37     inline P operator - (const P &X) const { 38         return P(x - X.x, y - X.y); 39     } 40     inline P operator * (const lf &X) const { 41         return P(x * X, y * X); 42     } 43     inline lf operator * (const P &X) const { 44         return x * X.y - y * X.x; 45     } 46     inline lf operator / (const P &X) const { 47         return x * X.x + y * X.y; 48     } 49     inline void read() { 50         scanf("%lf%lf", &x, &y); 51     } 52 }p[N], s[N], t[5]; 53   54 int n, top; 55 lf ans = 1e60; 56   57 inline lf sqr(lf x) { 58     return x * x; 59 } 60   61 inline lf dis(P a, P b) { 62     return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); 63 } 64   65 inline bool cmp_p(P a, P b) { 66     lf tmp = (a - p[1]) * (b - p[1]); 67     return fabs(tmp) < eps ? dis(a, p[1]) - dis(b, p[1]) < eps : tmp > -eps; 68 } 69   70 void graham() { 71     int i; 72     for (i = 2; i <= n; ++i) 73         if (p[i] < p[1]) swap(p[1], p[i]); 74     sort(p + 2, p + n + 1, cmp_p); 75     for (i = 2, s[top = 1] = p[1]; i <= n; ++i) { 76         while (top > 1 && (s[top] - s[top - 1]) * (p[i] - s[top]) < eps) --top; 77         s[++top] = p[i]; 78     } 79     s[0] = s[top]; 80 } 81   82 inline bool check_p(int i, int p) { 83     return (s[i + 1] - s[i]) * (s[p + 1] - s[i]) - (s[i + 1] - s[i]) * (s[p] - s[i]) > -eps; 84 } 85   86 inline bool check_r(int i, int r) { 87     return (s[i + 1] - s[i]) / (s[r + 1] - s[i]) - (s[i + 1] - s[i]) / (s[r] - s[i]) > -eps; 88 } 89   90 inline bool check_l(int i, int l) { 91     return (s[i + 1] - s[i]) / (s[l + 1] - s[i]) - (s[i + 1] - s[i]) / (s[l] - s[i]) < eps; 92 } 93   94 void work() { 95     int l, r, p, i; 96     lf L, R, H, D, tmp; 97     for (i = 0, l = r = p = 1; i < top; ++i) { 98         D = dis(s[i], s[i + 1]); 99         while (check_p(i, p)) (p += 1) %= top;100         while (check_r(i, r)) (r += 1) %= top;101         if (!i) l = r;102         while (check_l(i, l)) (l += 1) %= top;103         L = (s[i + 1] - s[i]) / (s[l] - s[i]) / D;104         R = (s[i + 1] - s[i]) / (s[r] - s[i]) / D;105         H = (s[i + 1] - s[i]) * (s[p] - s[i]) / D;106         if (H < 0) H = -H;107         tmp = (R - L) * H;108         if (tmp < ans) {109             ans = tmp;110             t[0] = s[i] + (s[i + 1] - s[i]) * (R / D);111             t[1] = t[0] + (s[r] - t[0]) * (H / dis(t[0], s[r]));112             t[2] = t[1] - (t[0] - s[i]) * ((R - L) / dis(s[i], t[0]));113             t[3] = t[2] - (t[1] - t[0]);114         }115     }116 }117  118 int main() {119     int i, st;120     scanf("%d", &n);121     for (i = 1; i <= n; ++i)122         p[i].read();123     graham();124     work();125     for (i = 1, st = 0; i <= 3; ++i)126         if (t[i] < t[st]) st = i;127     for (i = 0, printf("%.5lf\n", ans); i <= 3; ++i)128         printf("%.5lf %.5lf\n", t[(i + st) % 4].x, t[(i + st) % 4].y);129     return 0;130 }