Cod sursa(job #2051735)

Utilizator Coroian_DavidCoroian David Coroian_David Data 29 octombrie 2017 14:44:18
Problema Camera Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.98 kb
#include <bits/stdc++.h>

#define MAX_N 2000

using namespace std;

FILE *f;

int n;

struct coord
{
    long double x, y;
};

coord v[MAX_N + 2];

void readFile()
{
    f = fopen("camera.in", "r");

    fscanf(f, "%d", &n);

    int i;
    long double ld = 1.0D;
    int x, y;
    for(i = 1; i <= n; i ++)
    {
        fscanf(f, "%d%d", &x, &y);

        v[i] = {ld * x, ld * y};
    }

    long double a = 0;
    v[n + 1] = v[1];
    for(i = 1; i <= n; i ++)
        a += v[i].x * v[i + 1].y - v[i].y * v[i + 1].x;

    if(a < 0)
    {
        int mid = n >> 1;
        for(i = 1; i <= mid; i ++)
            swap(v[i], v[n - i + 1]);
    }

    v[n + 1] = v[1];

    fclose(f);
}

long double aria(coord a, coord b, coord c)
{
    ///x1 y1
    ///x2 y2
    ///1/2 *
    return a.x * b.y - a.y * b.x +
           b.x * c.y - b.y * c.x +
           c.x * a.y - c.y * a.x;
}

void getABC(coord p1, coord p2, long double &a, long double &b, long double &c)
{
    a = p2.y - p1.y;
    b = p1.x - p2.x;
    c = p2.x * p1.y - p1.x * p2.y;
}

coord getInter(coord p1, coord p2, coord p3, coord p4)
{
    long double a, b, c;
    long double d, e, f;

    getABC(p1, p2, a, b, c);
    getABC(p3, p4, d, e, f);

    coord rez;
    rez.y = (c * d - f * a) / (e * a - b * d);
    rez.x = (-c * e + f * b) / (e * a - b * d);

    return rez;
}

coord s[MAX_N + 2];
coord sn[MAX_N + 2];

long double getRez()
{
    int k = 4;
    s[1] = {-100000, -100000};
    s[2] = {100000, -100000};
    s[3] = {100000, 100000};
    s[4] = {-100000, 100000};

    long double ar1;
    long double ar2;
    int i, j;
    for(i = 1; i <= n; i ++)
    {
        coord d1, d2;
        d1 = v[i];
        d2 = v[i + 1];

        int nk = 0;
        s[k + 1] = s[1];
        for(j = 1; j <= k; j ++)
        {
            coord a, b;
            a = s[j];
            b = s[j + 1];

            ar1 = aria(d1, d2, a);
            ar2 = aria(d1, d2, b);

            if(ar1 * ar2 < 0.0D)
            {
                sn[++ nk] = getInter(d1, d2, a, b);

                if(ar2 > 0)///Nu punem acelasi punct de 2 ori
                    sn[++ nk] = b;
            }

            else
                if(ar2 >= 0)
                    sn[++ nk] = b;
        }

        for(j = 1; j <= nk; j ++)
            s[j] = sn[j];

        k = nk;
    }

    long double rez = 0.0D;
    s[k + 1] = s[1];
    for(i = 1; i <= k; i ++)
        rez += s[i].x * s[i + 1].y - s[i].y * s[i + 1].x;

    if(rez != 0.0D)
    {
        rez = fabsl(rez);
        rez /= 2.0D;
    }

    return rez;
}

long double rez;

void solve()
{
    ///Se intampla undefined daca bagi 2 functii in aceeasi linie de cod.
    rez = getRez();
}

void printFile()
{
    ofstream g("camera.out");

    g << fixed << setprecision(2) << rez << "\n";

    g.close();
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}