题解 P4166 【[SCOI2007]最大土地面积】

zsplj_ · 2019-05-14 15:37:56 · 题解

本题可以做到O(nlogn)，瓶颈在于求凸包。

首先这四个点肯定都在凸包上，所以首先求出凸包。

而且这个四边形的对角线的两个端点一定是对踵点，考虑旋转卡壳，O(n)枚举对角线P_u,P_v，并在枚举的过程中维护分别在对角线两侧，离对角线距离最远的点P_a,P_b。

容易发现这个过程中u,v,a,b都只对每个点扫了O(1)次，总时间复杂度为O(n)。

加上凸包的复杂度，总复杂度尾为O(nlogn)。

代码

（之前的代码出了写小错误，在枚举点u,v时,使用u+1,v+1没有进行模运算，已更正）

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

const double eps = 1e-10;

inline int dcmp(const double &x) {
    if (fabs(x) < eps) return 0; return x < 0 ? -1 : 1;
}

namespace geometry {
    using std::max;
    using std::sort;
    using std::unique;

    struct point {
        double x, y;
        point(double x = 0, double y = 0) : x(x), y(y) { }
        bool operator < (const point &b) const {
            return x != b.x ? x < b.x : y < b.y;
        }
    };
    typedef point vector;
    typedef std::vector<point> polygon;

    struct line {
        point p; vector v; double ang;
        line() {}
        line(point p, vector v) : p(p), v(v) { ang = atan2(v.y, v.x);}
        bool operator < (const line &b) const {
            return ang < b.ang;
        }
    };
    typedef std::vector<line> line_set;

    vector operator + (const vector &A, const vector &B) { return point(A.x + B.x, A.y + B.y);}
    vector operator - (const point &A, const point &B) { return point(A.x - B.x, A.y - B.y);}
    vector operator * (const vector &A, const double &b) { return vector(A.x * b, A.y * b);}
    vector operator / (const vector &A, const double &b) { return vector(A.x / b, A.y / b);}
    bool operator == (const point &A, const point &B) { return fabs(A.x - B.x) < eps && fabs(A.y - B.y) < eps;}

    inline double dot(const vector &A, const vector &B) { return A.x * B.x + A.y * B.y;}
    inline double cross(const vector &A, const vector &B) { return A.x * B.y - A.y * B.x;}
    inline double length(const vector &A) { return sqrt(dot(A, A));}
    inline double angle(const vector &A, const vector &B) { return acos(dot(A, B) / length(A) / length(B));}

    inline vector rotate(const vector &A, const double &rad) {
        double c = cos(rad), s = sin(rad);
        return vector(A.x * c - A.y * s, A.x * s + A.y * c);
    }

    inline vector normal(const vector &A) {
        double L = length(A); return vector(-A.y / L, A.x / L);
    }

    inline bool on_left(line L, point p) {
        return cross(L.v, p - L.p) > 0;
    }

    inline bool on_segment(point p, point a1, point a2) {
        return dcmp(cross(a1 - p, a2 - p) == 0) && dcmp(dot(a1 - p, a2 - p)) < 0;
    }

    inline bool segment_proper_intersection(point a1, point a2, point b1, point b2) {
        double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1),
               c3 = cross(b2 - b1, a1 - b1), c4 = cross(b2 - b1, a2 - b1);
        return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
    }

    int in_polygon(point p, polygon &poly) {
        int wn = 0;
        for (int i = 0, n = poly.size(); i < n; i++) {
            if (on_segment(p, poly[i], poly[i%n+1])) return -1;
            int k = dcmp(cross(poly[i%n+1] - poly[i], p - poly[i]));
            int d1 = dcmp(poly[i].y - p.y);
            int d2 = dcmp(poly[i%n+1].y - p.y);
            if (k > 0 && d1 <= 0 && d2 > 0) wn++;
            if (k < 0 && d2 <= 0 && d1 > 0) wn--;
        }
        if (wn != 0) return 1;
        return 0;
    }

    inline point line_intersection(point p, vector v, point q, vector w) {
        vector u = p - q; double t = cross(w, u) / cross(v, w);
        return p + v * t;
    }

    inline point line_intersection(line a, line b) {
        vector u = a.p - b.p; double t = cross(b.v, u) / cross(a.v, b.v);
        return a.p + a.v * t;
    }

    double distance_to_line(point p, point a, point b) {
        vector v1 = b - a, v2 = p - a;
        return fabs(cross(v1, v2)) / length(v1);
    }

    double distance_to_line(point p, line L) {
        vector v2 = p - L.p;
        return fabs(cross(L.p, v2)) / length(L.p);
    }

    double polygon_area(polygon &poly) {
        double ans = 0;
        for (int i = 1, n = poly.size(); i < n - 1; i++)
            ans += cross(poly[i] - poly[0], poly[i+1] - poly[0]);
        return ans / 2;
    }

    polygon convex_hull(polygon &p) {
        sort(p.begin(), p.end());
        p.erase(unique(p.begin(), p.end()), p.end());
        int m = 0, n = p.size(); polygon ch(n + 1);
        for (int i = 0; i < n; i++) {
            while (m > 1 && cross(ch[m-1] - ch[m-2], p[i] - ch[m-2]) <= 0) m--;
            ch[m++] = p[i];
        }
        for (int i = n - 2, k = m; i >= 0; i--) {
            while (m > k && cross(ch[m-1] - ch[m-2], p[i] - ch[m-2]) <= 0) m--;
            ch[m++] = p[i];
        }
        if (n > 1) m--; ch.resize(m);
        return ch;
    }

    polygon half_plane_intersection(line_set &L) {
        sort(L.begin(), L.end());
        int first, last, n = L.size();
        point *p = new point[n]; line *q = new line[n];
        q[first=last=0] = L[0];
        for (int i = 1; i < n; i++) {
            while (first < last && !on_left(L[i], p[last-1])) last--;
            while (first < last && !on_left(L[i], p[first])) first++;
            q[++last] = L[i];
            if (fabs(cross(q[last].v, q[last-1].v)) < eps)
                if (on_left(q[--last], L[i].p)) q[last] = L[i];
            if (first < last) p[last-1] = line_intersection(q[last-1], q[last]);
        }
        polygon ans;
        while (first < last && !on_left(q[first], p[last-1])) last--;
        if (last - first <= 1) return ans;
        p[last] = line_intersection(q[last], q[first]);
        for (int i = first; i <= last; i++) ans.push_back(p[i]);
        return ans;
    }
}

using namespace std;
using namespace geometry;

int n;
double ans;
polygon p;

inline void chkmx(int u, int v, int &a, int &b) {
    while ((a + 1) % n != v && distance_to_line(p[a+1], p[u], p[v]) > distance_to_line(p[a], p[u], p[v]))
        a = (a + 1) % n;
    while ((b + 1) % n != u && distance_to_line(p[b+1], p[u], p[v]) > distance_to_line(p[b], p[u], p[v]))
        b = (b + 1) % n;
    ans = max(ans,
          length(p[u] - p[v]) * (distance_to_line(p[b], p[u], p[v]) + distance_to_line(p[a], p[u], p[v])));
}

int main() {
    double x, y;
    cin >> n; p.resize(n);
    for (int i = 0; i < n; i++)
        cin >> x >> y, p[i] = point(x, y);
    p = convex_hull(p);

    n = p.size();
    for (int u = 0, v = 1, a = 0, b = 1; u < n; u++) {
        while (1) {
            int diff = dcmp(cross(p[(u+1)%n] - p[u], p[(v+1)%n] - p[v]));
            if (diff <= 0) {
                chkmx(u, v, a, b);
                if (diff == 0) chkmx(u, (v + 1) % n, a, b);
                break;
            }
            if (b == v) b = (b + 1) % n;
            v = (v + 1) % n;
        }
        if (a == u) a = (a + 1) % n;
    }
    printf("%.3lf\n", ans / 2);
}