一道计算几何裸题。。。调了蒟蒻两个小时。。。
问题出在求dis的时候忘了sqrt了，好了你现在可以退役滚蛋了，简直侮辱我们搞OI的人的智商
首先求个凸包出来，矩形的一边一定和凸包上一边重合。
然后枚举凸包上的边，用三个点同时旋转卡壳，卡出最小的矩形。
这题目写的我。。。醉了
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 ", ans); i <= 3; ++i) 128 printf("%.5lf %.5lf ", t[(i + st) % 4].x, t[(i + st) % 4].y); 129 return 0; 130 }