Cod sursa(job #42710)

Utilizator cromdioxidSasa Pastor cromdioxid Data 29 martie 2007 14:11:25
Problema Rubarba Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.9 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define NMAX 1001

using namespace std;

struct POINT
{
    int x, y;
};

const double INF = 100000.0;
POINT P[NMAX];
int U[NMAX], N, st[NMAX], len;
double Min;

struct comp
{
    bool operator()(POINT a, POINT b)
    {
        return a.y < b.y || a.y == b.y && a.x < b.x;
    }
};

int sgn(POINT a, POINT b, POINT c)
{
    int A, B, C;
    A = a.y - b.y;
    B = b.x - a.x;
    C = a.x*b.y - a.y*b.x;
    return (A*c.x + B*c.y + C);
}

double dist(double x1, double y1, double x2, double y2)
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int main()
{
    int i, inc, j, gasit, gasit2;
    double A1, B1, C1, A2, B2, C2, A3, B3, C3, A4, B4, C4, m1, m2;
    double x1, x2, x3, y1, y2, y3;
    double arie;
    POINT a, b, c;
    
    freopen("rubarba.in", "rt", stdin);
    freopen("rubarba.out", "wt", stdout);
    scanf("%d", &N);
    for (i = 0; i < N; i++)
        scanf("%d %d", &P[i].x, &P[i].y);
    sort(P, P+N, comp());
    st[0] = 0;
    st[1] = 1;
    U[1] = 1;
    len = 2;
    for (inc = 1, i = 2; i >= 0; i += inc)
    {
        if (U[i]) continue;
        while (len > 1 && sgn(P[ st[len - 1] ], P[ st[len - 2] ], P[i]) > 0)
            U[st[--len]] = 0;
        U[ st[len++] = i ] = 1;
        if (i == N - 1) inc *= -1;
    }
    len--;
    for (i = len; i < 2*len; i++)
        st[i] = st[i - len];
        
    B1 = B3 = B2 = B4 = -1;
    Min = INF;
    for (i = 0; i < len; i++)
    {
        a = P[ st[i] ];
        b = P[ st[i+1] ];
        m1 = (double) (a.y - b.y) / (a.x - b.x);
        A1 = A3 = m1;
        C1 = a.y - m1*a.x;

        m2 = -1/m1;
        A2 = A4 = m2;

        for (j = i + 2, gasit = gasit2 = 0; !gasit || !gasit2; j++)
        {
            c = P[ st[j] ];
            C4 = c.y - m2*c.x;

            a = P[ st[j-1] ];
            b = P[ st[j+1] ];
            if ((A4*a.x + B4*a.y + C4) * (A4*b.x + B4*b.y + C4) > 0)
                if (!gasit)
                    C2 = C4, gasit = 1;
                else
                    gasit2 = 1;
        }
        for (j = i + 2, gasit = 0; !gasit; j++)
        {
            c = P[ st[j] ];
            C3 = c.y - m1*c.x;

            a = P[ st[j-1] ];
            b = P[ st[j+1] ];
            if ((A3*a.x + B3*a.y + C3) * (A3*b.x + B3*b.y + C3) > 0)
                gasit = 1;
        }
        // aflare arie intersectie
        x1 = (B2*C1 - B1*C2) / (A2*B1 - A1*B2);
        y1 = (A1*C2 - A2*C1) / (A2*B1 - A1*B2);

        x2 = (B4*C1 - B1*C4) / (A4*B1 - A1*B4);
        y2 = (A1*C4 - A4*C1) / (A4*B1 - A1*B4);

        x3 = (B4*C3 - B3*C4) / (A4*B3 - A3*B4);
        y3 = (A3*C4 - A4*C3) / (A4*B3 - A3*B4);


        arie = dist(x1, y1, x2, x2) * dist(x1, y1, x3, y3);
        if (arie < Min)
            Min = arie;
    }
    printf("%lf\n", arie);
    return 0;
}