Cod sursa(job #1691430)

Utilizator sucureiSucureiRobert sucurei Data 18 aprilie 2016 12:51:51
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.09 kb
#include <fstream>
#include <cmath>
#include <iomanip>

using namespace std;

ifstream fin("camera.in");
ofstream fout("camera.out");

const double INF = 100000.0;
const double eps = 1e-6;

int N, M, P;
int sgn;

struct puncte
{
    double x, y;
};
puncte V[2005], A[2005], B[2005];

int cross_panta(puncte A, puncte B, puncte C)
{
    double val = (B.y - A.y) * (C.x - A.x) - (C.y - A.y) * (B.x - A.x);

    if (fabs(val) < eps)
        return 0;
    if (val >= eps)
        return 1;
    if (val <= -eps)
        return -1;
}

puncte intersect(puncte A, puncte B, puncte C, puncte D)
{
    double a1, b1, c1, a2, b2, c2;
    // (y2 - y1) * x + (x1 - x2) * y + (x2 * y1 - x1 * y2) = 0
    // a = y2 - y1
    // b = x1 - x2
    // c = (x2 * y1 - x1 * y2)

    a1 = B.y - A.y;
    b1 = A.x - B.x;
    c1 = B.x * A.y - A.x * B.y;

    a2 = D.y - C.y;
    b2 = C.x - D.x;
    c2 = D.x * C.y - C.x * D.y;

    puncte E;

    if (fabs((a1 * b2) - (a2 * b1)) < eps)
        E.x = (c2 * b1) - (c1 * b2);
    else
        E.x = ((c2 * b1) - (c1 * b2)) / ((a1 * b2) - (a2 * b1));

    if (fabs((a2 * b1) - (a1 * b2)) < eps)
        E.y = (a1 * c2) - (a2 * c1);
    else
        E.y = ((a1 * c2) - (a2 * c1)) / ((a2 * b1) - (a1 * b2));

    return E;
}

int arie()
{
    long long a = 0;
    for (int i = 1; i <= N; ++i)
        a += V[i].x * V[i + 1].y - V[i + 1].x * V[i].y;

    if (a > 0LL)
        return 1;
    return -1;
}

int main()
{
    fin >> N;
    for (int i = 1; i <= N; ++i)
        fin >> V[i].x >> V[i].y;
    V[N + 1] = V[1];

    int a = arie(); // ia sa vedem noi cum sunt punctele
    if (a > 0) // punctele sunt in ordine trigonometrica
        sgn = -1;
    else // punctele nu sunt in ordine trigonometrica(logic, daaaaa)
        sgn = 1;

    M = 4;
    A[1].x = -INF;
    A[1].y = -INF;
    A[2].x = INF;
    A[2].y = -INF;
    A[3].x = INF;
    A[3].y = INF;
    A[4].x = -INF;
    A[4].y = INF;
    A[5] = A[1];

    for (int i = 1; i <= N; ++i)
    {
        int cur, next;
        for (int j = 1; j <= M; ++j)
        {
            cur = j;
            next = j + 1;
            int s1 = cross_panta(V[i], V[i + 1], A[cur]);
            int s2 = cross_panta(V[i], V[i + 1], A[next]);

            if (s1 == sgn && s2 == sgn) // ambele sunt in interior
                B[++P] = A[next];
            else if (s1 == sgn && s2 != sgn) // cur e in interior, next e afara
                B[++P] = intersect(V[i], V[i + 1], A[cur], A[next]);
            else if (s1 != sgn && s2 == sgn) // cur e afara, next e in interior
            {
                B[++P] = intersect(V[i], V[i + 1], A[cur], A[next]);
                B[++P] = A[next];
            }
        }
        for (int j = 1; j <= P; ++j)
            A[j] = B[j];
        A[P + 1] = A[1];
        M = P;
        P = 0;
    }

    double sol = 0;
    for (int i = 1; i <= M; ++i)
        sol += A[i].x * A[i + 1].y - A[i + 1].x * A[i].y;
    fout << fixed << setprecision(2) << fabs(sol) / 2.0 << '\n';

    fin.close();
    fout.close();
    return 0;
}