Cod sursa(job #1384086)

Utilizator SmarandaMaria Pandele Smaranda Data 10 martie 2015 20:57:16
Problema Rubarba Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.66 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 100005;
const double eps = 1.e-14;

struct Point {
    double x, y;
};

Point LL;

int ccw (const Point &A, const Point &B, const Point &C) {
    double ans;

    ans = (A.x - C.x) * (B.y - C.y) - (A.y - C.y) * (B.x - C.x);
    if (ans <= -eps)
        return -1;
    if (ans > eps)
        return 1;
    return 0;
}

class MyComp {
    public :
        bool operator ()(const Point &A, const Point &B) {
            return ccw (LL, A, B) > 0;
        }
};

Point P [N], G, H, aux;
int hull [N];



double distance_point_line (const Point &A, const double &a, const double &b, const double &c) {
    double numitor, numarator;

    numitor = sqrt (a * a + b * b);
    numarator = fabs (a * A.x + b * A.y + c);
    return (double)numarator / numitor;
}

double dist (const Point &A, const Point &B) {
    return sqrt ((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

int main () {
    int n, i, u, g, i1, i2, i3;
    bool flag = 0;
    double a, b, c, d1, d2, c1, c2, l, w, ans, area, a1, b1, x1, y1, x2, y2;

    freopen ("rubarba.in", "r", stdin);
    freopen ("rubarba.out", "w", stdout);

    scanf ("%d", &n);
    LL.x = LL.y = (1ll << 31) - 1;
    for (i = 1; i <= n; i ++) {
        scanf ("%lf%lf", &P [i].x, &P [i].y);
        if (i == 1) {
            LL = P [i];
            x1 = x2 = P [i].x;
            y1 = y2 = P [i].y;
        }
        else {
            if (LL.y - P [i].y > eps || (fabs (LL.y - P [i].y) < eps && LL.x - P [i].x > eps)) {
                LL = P [i];
                aux = P [1];
                P [1] = P [i];
                P [i] = aux;
            }
            if (P [i].x - x1 <= -eps)
                x1 = P [i].x;
            if (P [i].y - y1 <= -eps)
                y1 = P [i].y;
            if (P [i].x - x2 > eps)
                x2 = P [i].x;
            if (P [i].y - y2 > eps)
                y2 = P [i].y;
        }
    }

    sort (P + 2, P + 1 + n, MyComp ());

    ans = (x2 - x1) * (y2 - y1);
    u = 0;
    hull [++ u] = 1;
    hull [++ u] = 2;
    P [n + 1] = P [1];
    for (i = 3; i <= n + 1; i ++) {
        g = ccw (P [hull [u - 1]], P [hull [u]], P [i]);
        if (g > 0)
            hull [++ u] = i;
        else {
            u --;
            while (u >= 2) {
                g = ccw (P [hull [u - 1]], P [hull [u]], P [i]);
                if (g > 0)
                    break;
                -- u;
            }
            hull [++ u] = i;
        }
    }

    hull [u] = hull [1];
    i1 = 1;
    i2 = 1;
    i3 = u - 1;
    -- u;
    for (i = 1; i <= u; i ++) {
        a = P [hull [i]].y - P [hull [i + 1]].y;
        b = P [hull [i + 1]].x - P [hull [i]].x;
        c = P [hull [i]].x * P [hull [i + 1]].y - P [hull [i]].y * P [hull [i + 1]].x;

        d1 = distance_point_line (P [hull [i1]], a, b, c);
        while (1) {
            ++ i1;
            if (i1 > u)
                i1 = 1;
            d2 = distance_point_line (P [hull [i1]], a, b, c);
            if (d2 - d1 <= -eps) {
                i1 --;
                if (i1 == 0)
                    i1 = u;
                break;
            }
            d1 = d2;
        }

        l = d1;

        c1 = b * P [hull [i2]].x - a * P [hull [i2]].y;
        while (1) {
            ++ i2;
            if (i2 > u)
                i2 = 1;
            c2 = b * P [hull [i2]].x - a * P [hull [i2]].y;
            if (c2 - c1 <= -eps) {
                i2 --;
                if (i2 == 0)
                    i2 = u;
                break;
            }
            c1 = c2;
        }

        c1 = - (a * P [hull [i2]].x + b * P [hull [i2]].y + c) / (a * a + b * b);
        H.x = c1 * a + P [hull [i2]].x;
        H.y = c1 * b + P [hull [i2]].y;
        w = dist (P [hull [i]], P [hull [i + 1]]) + dist (H, P [hull [i + 1]]);

        c1 = b * P [hull [i3]].x - a * P [hull [i3]].y;
        while (1) {
            ++ i3;
            if (i3 > u)
                i3 = 1;
            c2 = b * P [hull [i3]].x - a * P [hull [i3]].y;
            if (c2 - c1 > eps) {
                i3 --;
                if (i3 == 0)
                    i3 = u;
                break;
            }
            c1 = c2;
        }

        c1 = - (a * P [hull [i3]].x + b * P [hull [i3]].y + c) / (a * a + b * b);
        H.x = c1 * a + P [hull [i3]].x;
        H.y = c1 * b + P [hull [i3]].y;
        w += dist (H, P [hull [i]]);

        area = l * w;

            if (area - ans <= -eps)
                ans = area;
    }
    printf ("%.2lf\n", ans);
    return 0;
}