2010-1096

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

这是一道old题，原题在[http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1185 这里]
题意是给50000个点，求最小矩形能覆盖这些点。

首先对于这50000个点求一个凸包，则可以证明矩形必有一条边和凸包上的边重合。剩下的就是旋转卡壳的经典问题了。具体旋转卡壳的资料可以在网上搜。
{{{
#!cpp
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cassert>

using namespace std;

const double EPS = 1e-8;
const int MAXN = 50005;

struct Point {
    double x, y;
    Point() {}
    Point(double x, double y) :x(x), y(y) {}
};

inline Point operator + (const Point& a, const Point& b) {
    return Point(a.x + b.x, a.y + b.y);
}

inline Point operator - (const Point& a, const Point& b) {
    return Point(a.x - b.x, a.y - b.y);
}

inline Point operator * (const Point& a, const double k) {
    return Point(a.x * k, a.y * k);
}

inline Point operator / (const Point& a, const double k) {
    return Point(a.x / k, a.y / k);
}

inline bool zero(double x) {
    return ((x > 0 ? x : -x) < EPS);
}

inline bool eq(double x, double y) {
    return x < y + EPS && y < x + EPS;
}

inline double xmult(const Point & p1, const Point & p2, const Point & p0) {
    return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}

inline double dmult(const Point & p1, const Point & p2, const Point & p0) {
    return (p1.x - p0.x) * (p2.x - p0.x) + (p1.y - p0.y) * (p2.y - p0.y);
}

inline double dis(const Point & p1, const Point & p2) {
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}

inline bool cmp(const Point& a, const Point& b) {
    return zero(a.y - b.y) ? (a.x > b.x + EPS) : (a.y > b.y + EPS);
}

inline int graham(int n, Point p[], Point ch[], bool maxsize = false) {
    const double e1 = maxsize ? EPS : -EPS;
    int i, j, k;
    if (n < 3) {
        for(i = 0; i < n; i++) {
            ch[i] = p[i];
        }
        return n;
    }
    sort(p, p + n, cmp);
    ch[0] = p[0];
    ch[1] = p[1];
    for (i = j = 2; i < n; ch[j++] = p[i++]) {
        while (j > 1 && xmult(ch[j - 2], p[i], ch[j - 1]) > e1) {
            j--;
        }
    }
    ch[k = j++] = p[n - 2];
    for (i = n - 3; i > 0; ch[j++] = p[i--]) {
        while (j > k && xmult(ch[j - 2], p[i], ch[j - 1]) > e1) {
            j--;
        }
    }
    while (j > k && xmult(ch[j - 2], ch[0], ch[j - 1]) > e1) {
        j--;
    }
    return j;
}

inline Point intersection(const Point & u1, const Point & u2, const Point & v1, const Point & v2) {
    Point ret = u1;
    double t = ((u1.x - v1.x) * (v1.y - v2.y) - (u1.y - v1.y) * (v1.x - v2.x)) / ((u1.x - u2.x) * (v1.y - v2.y) - (u1.y - u2.y) * (v1.x - v2.x));
    ret.x += (u2.x - u1.x) * t;
    ret.y += (u2.y - u1.y) * t;
    return ret;
}

inline Point ptoline(const Point & p, const Point & l1, const Point & l2) {
    Point t = p;
    t.x += l1.y - l2.y;
    t.y += l2.x - l1.x;
    return intersection(p, t, l1, l2);
}

inline double disptoline(const Point & p, const Point & l1, const Point & l2) {
    return fabs(xmult(p, l1, l2)) / dis(l1, l2);
}

int n;
int next[MAXN];
Point p[MAXN], ch[MAXN];

inline double times(const Point& p, const Point& a, const Point& b) {
    if (fabs(a.y - b.y) > fabs(a.x - b.x)) {
        return (p.y - a.y) / (b.y - a.y);
    } else {
        return (p.x - a.x) / (b.x - a.x);
    }
}

inline void generate(const Point& p1, const Point& p2, const Point& p3, const Point& p4, const Point& p5,
                    double& area, Point* p) {
    p[0] = ptoline(p5, p1, p2);
    p[1] = ptoline(p3, p1, p2);
    Point r = p2 - p1 + p4;
    p[2] = ptoline(p3, p4, r);
    p[3] = ptoline(p5, p4, r);
    double t = disptoline(p4, p1, p2);
    area = dis(p[0], p[1]) * t;
}

int main() {
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++) {
            scanf("%lf%lf", &ch[i].x, &ch[i].y);
        }
        n = graham(n, ch, p);
        for (int i = 0; i < n; i++) {
            next[i] = (i + 1) % n;
        }
        int b = 1, c = 1, d = 0;
        for (int i = 2; i < n; i++) {
            Point t = ptoline(p[i], p[0], p[1]);
            if (times(t, p[0], p[1]) > times(ptoline(p[b], p[0], p[1]), p[0], p[1])) {
                b = i;
            }
            if (times(t, p[1], p[0]) > times(ptoline(p[d], p[0], p[1]), p[1], p[0])) {
                d = i;
            }
            if (disptoline(p[i], p[0], p[1]) > disptoline(p[c], p[0], p[1])) {
                c = i;
            }
        }
        double resa = 1e100;
        Point resp[4];
        for (int i = 0; i < n; i++) {
            int k = next[i];
            while (times(ptoline(p[next[b]], p[i], p[k]), p[i], p[k]) > times(ptoline(p[b], p[i], p[k]), p[i], p[k])) {
                b = next[b];
            }
            while (times(ptoline(p[next[d]], p[i], p[k]), p[k], p[i]) > times(ptoline(p[d], p[i], p[k]), p[k], p[i])) {
                d = next[d];
            }
            while (disptoline(p[next[c]], p[i], p[k]) > disptoline(p[c], p[i], p[k])) {
                c = next[c];
            }
            double area;
            Point point[4];
            generate(p[i], p[k], p[b], p[c], p[d], area, point);
            if (area < resa) {
                resa = area;
                memcpy(resp, point, sizeof(resp));
            }
        }
        printf("%.5lf\n", fabs(resa));
        while (true) {
            bool flag = true;
            for (int i = 1; i < 4 && flag; i++) {
                if (resp[0].y > resp[i].y + EPS || (eq(resp[0].y, resp[i].y) && resp[0].x > resp[i].x + EPS)) {
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
            Point t = resp[0];
            for (int i = 0; i < 3; i++) {
                resp[i] = resp[i + 1];
            }
            resp[3] = t;
        }
        for (int i = 0; i < 4; i++) {
            if (zero(resp[i].x)) {
                resp[i].x = fabs(resp[i].x);
            }
            if (zero(resp[i].y)) {
                resp[i].y = fabs(resp[i].y);
            }
        }
        for (int i = 0; i < 4; i++) {
            printf("%.5lf %.5lf\n", resp[i].x, resp[i].y);
        }
    }
    return 0;
}
}}}

这是一道old题，原题在这里

题意是给50000个点，求最小矩形能覆盖这些点。

首先对于这50000个点求一个凸包，则可以证明矩形必有一条边和凸包上的边重合。剩下的就是旋转卡壳的经典问题了。具体旋转卡壳的资料可以在网上搜。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cassert>
using namespace std;
const double EPS = 1e-8;
const int MAXN = 50005;
struct Point {
    double x, y;
    Point() {}
    Point(double x, double y) :x(x), y(y) {}
};
inline Point operator + (const Point& a, const Point& b) {
    return Point(a.x + b.x, a.y + b.y);
}
inline Point operator - (const Point& a, const Point& b) {
    return Point(a.x - b.x, a.y - b.y);
}
inline Point operator * (const Point& a, const double k) {
    return Point(a.x * k, a.y * k);
}
inline Point operator / (const Point& a, const double k) {
    return Point(a.x / k, a.y / k);
}
inline bool zero(double x) {
    return ((x > 0 ? x : -x) < EPS);
}
inline bool eq(double x, double y) {
    return x < y + EPS && y < x + EPS;
}
inline double xmult(const Point & p1, const Point & p2, const Point & p0) {
    return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}
inline double dmult(const Point & p1, const Point & p2, const Point & p0) {
    return (p1.x - p0.x) * (p2.x - p0.x) + (p1.y - p0.y) * (p2.y - p0.y);
}
inline double dis(const Point & p1, const Point & p2) {
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
inline bool cmp(const Point& a, const Point& b) {
    return zero(a.y - b.y) ? (a.x > b.x + EPS) : (a.y > b.y + EPS);
}
inline int graham(int n, Point p[], Point ch[], bool maxsize = false) {
    const double e1 = maxsize ? EPS : -EPS;
    int i, j, k;
    if (n < 3) {
        for(i = 0; i < n; i++) {
            ch[i] = p[i];
        }
        return n;
    }
    sort(p, p + n, cmp);
    ch[0] = p[0];
    ch[1] = p[1];
    for (i = j = 2; i < n; ch[j++] = p[i++]) {
        while (j > 1 && xmult(ch[j - 2], p[i], ch[j - 1]) > e1) {
            j--;
        }
    }
    ch[k = j++] = p[n - 2];
    for (i = n - 3; i > 0; ch[j++] = p[i--]) {
        while (j > k && xmult(ch[j - 2], p[i], ch[j - 1]) > e1) {
            j--;
        }
    }
    while (j > k && xmult(ch[j - 2], ch[0], ch[j - 1]) > e1) {
        j--;
    }
    return j;
}
inline Point intersection(const Point & u1, const Point & u2, const Point & v1, const Point & v2) {
    Point ret = u1;
    double t = ((u1.x - v1.x) * (v1.y - v2.y) - (u1.y - v1.y) * (v1.x - v2.x)) / ((u1.x - u2.x) * (v1.y - v2.y) - (u1.y - u2.y) * (v1.x - v2.x));
    ret.x += (u2.x - u1.x) * t;
    ret.y += (u2.y - u1.y) * t;
    return ret;
}
inline Point ptoline(const Point & p, const Point & l1, const Point & l2) {
    Point t = p;
    t.x += l1.y - l2.y;
    t.y += l2.x - l1.x;
    return intersection(p, t, l1, l2);
}
inline double disptoline(const Point & p, const Point & l1, const Point & l2) {
    return fabs(xmult(p, l1, l2)) / dis(l1, l2);
}
int n;
int next[MAXN];
Point p[MAXN], ch[MAXN];
inline double times(const Point& p, const Point& a, const Point& b) {
    if (fabs(a.y - b.y) > fabs(a.x - b.x)) {
        return (p.y - a.y) / (b.y - a.y);
    } else {
        return (p.x - a.x) / (b.x - a.x);
    }
}
inline void generate(const Point& p1, const Point& p2, const Point& p3, const Point& p4, const Point& p5,
                    double& area, Point* p) {
    p[0] = ptoline(p5, p1, p2);
    p[1] = ptoline(p3, p1, p2);
    Point r = p2 - p1 + p4;
    p[2] = ptoline(p3, p4, r);
    p[3] = ptoline(p5, p4, r);
    double t = disptoline(p4, p1, p2);
    area = dis(p[0], p[1]) * t;
}
int main() {
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++) {
            scanf("%lf%lf", &ch[i].x, &ch[i].y);
        }
        n = graham(n, ch, p);
        for (int i = 0; i < n; i++) {
            next[i] = (i + 1) % n;
        }
        int b = 1, c = 1, d = 0;
        for (int i = 2; i < n; i++) {
            Point t = ptoline(p[i], p[0], p[1]);
            if (times(t, p[0], p[1]) > times(ptoline(p[b], p[0], p[1]), p[0], p[1])) {
                b = i;
            }
            if (times(t, p[1], p[0]) > times(ptoline(p[d], p[0], p[1]), p[1], p[0])) {
                d = i;
            }
            if (disptoline(p[i], p[0], p[1]) > disptoline(p[c], p[0], p[1])) {
                c = i;
            }
        }
        double resa = 1e100;
        Point resp[4];
        for (int i = 0; i < n; i++) {
            int k = next[i];
            while (times(ptoline(p[next[b]], p[i], p[k]), p[i], p[k]) > times(ptoline(p[b], p[i], p[k]), p[i], p[k])) {
                b = next[b];
            }
            while (times(ptoline(p[next[d]], p[i], p[k]), p[k], p[i]) > times(ptoline(p[d], p[i], p[k]), p[k], p[i])) {
                d = next[d];
            }
            while (disptoline(p[next[c]], p[i], p[k]) > disptoline(p[c], p[i], p[k])) {
                c = next[c];
            }
            double area;
            Point point[4];
            generate(p[i], p[k], p[b], p[c], p[d], area, point);
            if (area < resa) {
                resa = area;
                memcpy(resp, point, sizeof(resp));
            }
        }
        printf("%.5lf\n", fabs(resa));
        while (true) {
            bool flag = true;
            for (int i = 1; i < 4 && flag; i++) {
                if (resp[0].y > resp[i].y + EPS || (eq(resp[0].y, resp[i].y) && resp[0].x > resp[i].x + EPS)) {
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
            Point t = resp[0];
            for (int i = 0; i < 3; i++) {
                resp[i] = resp[i + 1];
            }
            resp[3] = t;
        }
        for (int i = 0; i < 4; i++) {
            if (zero(resp[i].x)) {
                resp[i].x = fabs(resp[i].x);
            }
            if (zero(resp[i].y)) {
                resp[i].y = fabs(resp[i].y);
            }
        }
        for (int i = 0; i < 4; i++) {
            printf("%.5lf %.5lf\n", resp[i].x, resp[i].y);
        }
    }
    return 0;
}