Cod sursa(job #2051722)

Utilizator Coroian_DavidCoroian David Coroian_David Data 29 octombrie 2017 14:25:13
Problema Camera Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.66 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};
    }

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

      //  cout << fixed << setprecision(6) << "INTER " << rez.x << " " << rez.y << "\n";
    return rez;
}

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

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

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

       // cout << "DREAPTA \n";
       // cout << fixed << setprecision(6) << d1.x << " " << d1.y << "\n";
       // cout << fixed << setprecision(6) << d2.x << " " << d2.y << "\n";
        int nk = 0;
        s[k + 1] = s[1];
        for(j = 1; j <= k; j ++)
        {
       // cout << fixed << setprecision(6) << s[j].x << " " << s[j].y << "\n";

       // cout << fixed << setprecision(6) << s[j + 1].x << " " << s[j + 1].y << "\n";
            coord a, b;
            a = s[j];
            b = s[j + 1];

            ar = aria(d1, d2, a);
            int p1 = (((ar < 0.0D) == (sign < 0.0D)) || ar == 0);
            ar = aria(d1, d2, b);
            int p2 = (((ar < 0.0D) == (sign < 0.0D)) || ar == 0);

            if((p1 + p2) == 1)
            {
                sn[++ nk] = getInter(d1, d2, a, b);
            }

            if(p2 == 1)
                sn[++ nk] = b;//, cout << "BAGA DOILEA \n";

            //if(p2 == 1)
            //    sn[++ nk] = b;
        }
       // cout << "GATA\n";

        for(j = 1; j <= nk; j ++)
            s[j] = sn[j];
       // cout << fixed << setprecision(6) << s[j].x << " " << s[j].y << "\n";;

            //cout << "NOI\n";

        k = nk;
    }

    long double rez = 0.0D;

    //cout << k << "\n";


  //      cout << fixed << setprecision(6) << rez<< "\n";
    s[k + 1] = s[1];
    for(i = 1; i <= k; i ++)
    {
//        cout << fixed << setprecision(6) << s[i].x << " " << s[i].y << "\n";

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

   // cout << rez << "\n";

    return rez;
}

long double rez;

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

    long double r1 = getRez(-1);

  //  cout << rez << " " << r1 << "\n";

    rez = max(rez, r1);
}

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

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

    g.close();
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}