Cod sursa(job #875066)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 9 februarie 2013 17:41:56
Problema Reuniune Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.8 kb
#include <fstream>
#include <stdio.h>
#include <assert.h>
using namespace std;

const int OO = (1 << 31) - 1;
const double err = 0.00001;
int LD[5], NLIX, NLIY;
double LIX[5], LIY[5], A, P;
struct dreptunghi { double x[4], y[4]; } D[5];

void sort_dreptunghi (dreptunghi &d)
{
    double x1 = d.x[0], x2 = d.x[0];
    double y1 = d.y[0], y2 = d.y[0];

    for (int i = 1; i < 4; i++)
    {
        x1 = min (x1, d.x[i]);
        y1 = min (y1, d.y[i]);
        x2 = max (x2, d.x[i]);
        y2 = max (y2, d.y[i]);
    }

    d.x[0] = d.x[3] = x1;
    d.x[1] = d.x[2] = x2;
    d.y[0] = d.y[1] = y1;
    d.y[2] = d.y[3] = y2;
}

int cauta (int x, int y)
{
    for (int i = 1; i <= NLIX; i++)
    {
        if (LIX[i] == x && LIY[i] == y)
        {
            return 1;
        }
    }
    return 0;
}

double abs_double (double a)
{
    if (a < 0)
        return -a;
    return a;
}

long long rotunjeste (double a)
{
    if (abs_double (a - (long long)(a + 1)) < 0.5)
        return (long long)a + 1;
    return (long long)a;
}

double arie (double x1, double y1, double x2, double y2, double x3, double y3)
{
    return abs_double ((x3 - x2) * (y1 - y2) - (x1 - x2) * (y3 - y2));
}

double arie_d (dreptunghi d)
{
    double v = 0;

    v += arie (d.x[0], d.y[0], d.x[1], d.y[1], d.x[2], d.y[2]);
    v += arie (d.x[0], d.y[0], d.x[3], d.y[3], d.x[2], d.y[2]);

    return v;
}

double perimetru (dreptunghi d)
{
    double v = 0;
    for (int i = 0; i < 4; i++)
    {
        v += abs_double (d.x[i] - d.x[(i+1)&3]);
        v += abs_double (d.y[i] - d.y[(i+1)&3]);
    }
    return v;
}

int in_pd (double x, double y, dreptunghi d)
{
    //returneaza 1 daca (x, y) e in interiorul dreptunghiului cu indicele d2
    double v1 = 0, v2 = 0;

    v2 = arie_d (d);
    for (int i = 0; i < 4; i++)
    {
        v1 += arie (x, y, d.x[i], d.y[i], d.x[(i+1)&3], d.y[(i+1)&3]);
    }

    return v1 == v2;//v1 - err < v2 && v2 < v1 + err;
}

int in_d (double xi, double x1, double x2)
{
    double v1 = abs_double (xi - x1) + abs_double (xi - x2);
    double v2 = abs_double (x2 - x1);
    return v1 == v2;//v1 - err < v2 && v2 < v1 + err;
}

int in_dd (double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4, double &xi, double &yi)
{
    //returneaza 1 daca segmentele date de cele 4 puncte se intersecteaza
    //in xi si yi va returna valorile intersectiilor
    double m1, m2, n1, n2;
    if (x1 == x2)
    {
        m1 = OO;
    }
    else
    {
        m1 = (y1 - y2) / (x1 - x2);
        n1 = (x1 * y2 - x2 * y1) / (x1 - x2);
    }

    if (x3 == x4)
    {
        m2 = OO;
    }
    else
    {
        m2 = (y3 - y4) / (x3 - x4);
        n2 = (x3 * y4 - x4 * y3) / (x3 - x4);
    }
    if (m1 == m2)
        return 0;

    if (m1 == OO)
    {
        xi = x1;
        yi = m2 * xi + n2;
    }
    else if (m2 == OO)
    {
        xi = x3;
        yi = m1 * xi + n1;
    }
    else
    {
        xi = (n2 - n1) / (m1 - m2);
        yi = (m1 * n2 - m2 * n1) / (m1 - m2);
    }

    if ( !(in_d (xi, x1, x2) && in_d (xi, x3, x4) && in_d (yi, y1, y2) && in_d (yi, y3, y4)) )
        return 0;
    return 1;
}

void cit ()
{
    for (int i = 0; i < 3; i++)
    {
        scanf ("%llf%llf%llf%llf", &D[i].x[0], &D[i].y[0], &D[i].x[2], &D[i].y[2]);
        D[i].x[1] = D[i].x[2];
        D[i].y[1] = D[i].y[0];
        D[i].x[3] = D[i].x[0];
        D[i].y[3] = D[i].y[2];
    }
}

void rez ()
{
    int d1, d2, d3, id1, id2, id3, p1, p2, i, b, ok;
    double xi, yi, dA, dP;
    for (i = 1; i < 1 << 3; i++)
    {
        LD[0] = 0;
        NLIX = 0;
        NLIY = 0;

        for (b = 0; b < 3; b++)
        {
            if ((i >> b) & 1)
            {
                LD[++LD[0]] = b;
            }
        }

        for (id1 = 1; id1 <= LD[0]; id1++)
        {
            d1 = LD[id1];
            for (p1 = 0; p1 < 4; p1++)
            {
                ok = 1;
                for (id2 = 1; id2 <= LD[0]; id2++)
                {
                    d2 = LD[id2];
                    if (!in_pd (D[d1].x[p1], D[d1].y[p1], D[d2]))
                    {
                        ok = 0;
                    }
                }
                if (ok)
                {
                    if (cauta (D[d1].x[p1], D[d1].y[p1]))
                        continue;

                    LIX[++NLIX] = D[d1].x[p1];
                    LIY[++NLIY] = D[d1].y[p1];
                }
            }
        }

        for (id1 = 1; id1 < LD[0]; id1++)
        {
            d1 = LD[id1];
            for (p1 = 0; p1 < 4; p1++)
            {
                for (p2 = 0; p2 < 4; p2++)
                {
                    for (id2 = id1 + 1; id2 <= LD[0]; id2++)
                    {
                        d2 = LD[id2];
                        if (in_dd (D[d1].x[p1], D[d1].y[p1], D[d1].x[(p1+1)&3], D[d1].y[(p1+1)&3],
                                   D[d2].x[p2], D[d2].y[p2], D[d2].x[(p2+1)&3], D[d2].y[(p2+1)&3], xi, yi))
                        {
                            ok = 1;
                            for (id3 = 1; id3 <= LD[0]; id3++)
                            {
                                d3 = LD[id3];
                                if (!in_pd (xi, yi, D[d3]))
                                {
                                    ok = 0;
                                }
                            }
                            if (ok)
                            {
                                if (cauta (xi, yi))
                                    continue;

                                LIX[++NLIX] = xi;
                                LIY[++NLIY] = yi;
                            }
                        }
                    }
                }
            }
        }

        if (NLIX == 0)
        {
            continue;
        }
        if (NLIX > 4)
        {
            assert (0);
        }
        while (NLIX < 4)
        {
            LIX[++NLIX] = LIX[1];
            LIY[++NLIY] = LIY[1];
        }

        for (p1 = 0; p1 < 4; p1++)
        {
            D[4].x[p1] = LIX[p1 + 1];
            D[4].y[p1] = LIY[p1 + 1];
        }
        sort_dreptunghi (D[4]);

        dA = arie_d (D[4]) / 2.0;
        dP = perimetru (D[4]);

        if ((LD[0] & 1) == 0)
        {
            dA = -1.0 * dA;
            dP = -1.0 * dP;
        }

        A += dA;
        P += dP;
    }
}

void afi ()
{
    long long a = (long long)(A + err);
    long long p = (long long)(P + err);
    printf ("%lld ", a);
    printf ("%lld ", p);
}

int main ()
{
    freopen ("reuniune.in", "r", stdin);
    freopen ("reuniune.out", "w", stdout);

    cit ();
    rez ();
    afi ();

    return 0;
}