Cod sursa(job #1384002)

Utilizator SmarandaMaria Pandele Smaranda Data 10 martie 2015 19:56:53
Problema Rubarba Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.18 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;
    double alpha;
};

class MyComp {
    public :
        bool operator ()(const Point &A, const Point &B) {
            return A.alpha - B.alpha <= -eps;
        }
};

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

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

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

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 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));
}

bool insegment (const Point &C, const Point &A, const Point &B) {
    double x1, x2, y1, y2;

    x1 = A.x;
    y1 = A.y;
    x2 = B.x;
    y2 = B.y;
    if (B.x - x1 <= -eps) {
        x1 = B.x;
        x2 = A.x;
    }
    if (B.y - y1 <= -eps) {
        y1 = B.y;
        y2 = A.y;
    }
    if ((C.x - x1 > eps || fabs (C.x - x1) < eps) && (C.x - x2 <= -eps || fabs (C.x - x2) < eps) && (C.y - y1 > eps || fabs (C.y - y1) < eps) && (C.y - y2 <= -eps || fabs (C.y - y2) < eps))
        return 1;
    return 0;
}

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;

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

    scanf ("%d", &n);
    G.x = G.y = 0;
    for (i = 1; i <= n; i ++) {
        scanf ("%lf%lf", &P [i].x, &P [i].y);
        G.x = G.x + P [i].x;
        G.y = G.y + P [i].y;
    }

    G.x = G.x / n;
    G.y = G.y / n;

    for (i = 1; i <= n; i ++)
        P [i].alpha = atan2 (P [i].y - G.y, P [i].x - G.x);

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

    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 = 2;
    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 = P [hull [i2]].x * (a + b) + P [hull [i2]].y * (b - a) + c;
        while (1) {
            ++ i2;
            if (i2 > u)
                i2 = 1;
            c2 = P [hull [i2]].x * (a + b) + P [hull [i2]].y * (b - a) + c;
            if (c2 - c1 > eps) {
                i2 --;
                if (i2 <= 0)
                    i2 = u;
                break;
            }
            c1 = c2;
        }
        */
        i2 = i + 2;
        if (i2 > u)
            i2 = i2 - u;
        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;

        if (insegment (H, P [hull [i]], P [hull [i + 1]]))
            w = dist (P [hull [i]], P [hull [i + 1]]);
        else
            w = dist (P [hull [i]], P [hull [i + 1]]) + dist (H, P [hull [i + 1]]);

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

        i3 = i - 1;
        if (i3 == 0)
            i3 = u;
        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;

        if (insegment (H, P [hull [i]], P [hull [i + 1]]))
            w += 0;
        else
            w += dist (H, P [hull [i]]);

        area = l * w;
        if (flag == 0) {
            ans = area;
            flag = 1;
        }
        else
            if (area - ans <= -eps)
                ans = area;
    }
    printf ("%.3lf", ans);
    return 0;
}