题目链接 https://www.luogu.org/problemnew/show/P3187
嗯, 毒瘤题.
首先有一个结论, 就是最小矩形一定有条边和凸包重合. 脑补一下就好了.
然后枚举凸包的边, 用旋转卡壳维护上顶点, 左端点, 右端点就好了.
上顶点用叉积, 叉积越大三角形面积越大, 对应的高也就越大. 两边的点用点积, 点积越大投影越大.
然后就是精度问题. 这种实数计算最好不要直接用比较运算符, 要用差和 \(eps\) 的关系来比较, 我就是一直卡在这里. 还好有爆炸 \(OJ\) 离线题库提供的数据...
- #include <cstdio>
- #include <cmath>
- #include <algorithm>
- using namespace std;
- const int MAXN = 50010;
- const double eps = 1e-8;
- struct point{
- double x, y;
- inline double dis(){
- return sqrt(x * x + y * y);
- }
- inline void print(){
- if(fabs(x) <1e-10) x = 0;
- if(fabs(y) < 1e-10) y = 0;
- printf("%.5lf %.5lf\n", x, y);
- }
- }p[MAXN];
- inline double sig(double x){
- return (x> eps) - (x <-eps);
- }
- int operator == (point a, point b){
- return a.x == b.x && a.y == b.y;
- }
- point operator * (point a, double b){ // ba
- return (point){ a.x * b, a.y * b };
- }
- double operator * (point a, point b){ // a x b
- return a.x * b.y - b.x * a.y;
- }
- double operator / (point a, point b){ // a . b
- return a.x * b.x + a.y * b.y;
- }
- point operator - (point a, point b){ // a - b
- return (point){ a.x - b.x, a.y - b.y };
- }
- point operator + (point a, point b){ // a + b
- return (point){ a.x + b.x, a.y + b.y };
- }
- int cmp(const point a, const point b){
- return a.x == b.x ? a.y < b.y : a.x < b.x;
- }
- inline int judge(point a, point b, point c){ //Kab> Kac
- return (b.y - a.y) * (c.x - a.x)> (c.y - a.y) * (b.x - a.x);
- }
- inline double mult(point a, point b, point c){
- return (a - c) * (b - c);
- }
- inline double calc(point a, point b, point c){
- return (b - a) / (c - a);
- }
- int n, top, tp;
- point st[MAXN], ts[MAXN], Ans[5];
- double ans = 1e18, d, a, b, L, R;
- int main(){
- scanf("%d", &n);
- for(int i = 1; i <= n; ++i)
- scanf("%lf%lf", &p[i].x, &p[i].y);
- sort(p + 1, p + n + 1, cmp);
- for(int i = 1; i <= n; ++i){
- if(p[i] == p[i - 1]) continue;
- while(top> 1 && judge(st[top - 1], st[top], p[i])) --top;
- st[++top] = p[i];
- }
- for(int i = 1; i <= n; ++i){
- if(p[i] == p[i - 1]) continue;
- while(tp> 1 && !judge(ts[tp - 1], ts[tp], p[i])) --tp;
- ts[++tp] = p[i];
- }
- for(int i = tp - 1; i; --i) st[++top] = ts[i];
- --top;
- int j = 2, k = 2, l = 2;
- for(int i = 1; i <= top; ++i){
- while(sig(mult(st[i], st[i + 1], st[j]) - mult(st[i], st[i + 1], st[j + 1])) <= 0) if(++j> top) j = 1;
- while(sig(calc(st[i], st[i + 1], st[k]) - calc(st[i], st[i + 1], st[k + 1])) <= 0) if(++k> top) k = 1;
- if(i == 1) l = k;
- while(sig(calc(st[i], st[i + 1], st[l]) - calc(st[i], st[i + 1], st[l + 1]))>= 0) if(++l> top) l = 1;
- d = (st[i] - st[i + 1]).dis();
- R = calc(st[i], st[i + 1], st[k]) / d;
- L = calc(st[i], st[i + 1], st[l]) / d;
- b = fabs(mult(st[i], st[i + 1], st[j]) / d);
- a = R - L;
- if(a * b < ans){
- ans = a * b;
- Ans[1] = st[i] + (st[i + 1] - st[i]) * (R / d);
- Ans[2] = Ans[1] + (st[k] - Ans[1]) * (b / (st[k] - Ans[1]).dis());
- Ans[3] = Ans[2] + (st[i] - Ans[1]) * (a / R);
- Ans[4] = Ans[3] + (Ans[1] - Ans[2]);
- }
- }
- printf("%.5lf\n", ans);
- double Min = 1e18, pos;
- for(int i = 1; i <= 4; ++i)
- if(Ans[i].y < Min)
- Min = Ans[i].y, pos = i;
- for(int i = pos; i <= 4; ++i)
- Ans[i].print();
- for(int i = 1; i < pos; ++i)
- Ans[i].print();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2933992.html