Cod sursa(job #1759888)

Utilizator akaprosAna Kapros akapros Data 19 septembrie 2016 22:59:49
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.35 kb
#include <bits/stdc++.h>
#define maxN 2002
#define pii pair < double, double >
#define f first
#define s second
#define mp make_pair
#define inf 1000000.0
#define Inf -2000000.0
#define e 0.000001
using namespace std;
int n, m, p, sg;
pii v[3][maxN];
double ans;
void copy21()
{
    int i;
    m = p;
    for (i = 1; i <= m; ++ i)
        v[1][i] = v[2][i];
    v[1][m + 1] = v[1][1];
}
int sign(pii a, pii b, pii c)
{
    double A = a.s - b.s;
    double B = b.f - a.f;
    double C = - b.f * a.s + b.s * a.f;
    if (A * c.f + B * c.s + C > -e)
        return 1;
    if (A * c.f + B * c.s + C < e)
        return -1;
    return 0;
}
double A(int t)
{
    int i;
    double aria = 0.0;
    if (t == 1)
        n = m;
    for (i = 1; i <= n; ++ i)
        aria += v[t][i].f * v[t][i + 1].s - v[t][i + 1].f * v[t][i].s;
    return 0.5 * aria;
}
pii inters(pii a, pii b, pii c, pii d)
{
    double a1, b1, c1, a2, b2, c2;
    a1 = b.s - a.s;
    a2 = d.s - c.s;
    b1 = a.f - b.f;
    b2 = c.f - d.f;
    c1 = a1 * a.f + b1 * a.s;
    c2 = a2 * c.f + b2 * c.s;

    if (fabs(a1 * b2 - a2 * b1) < e)
        return mp(Inf, Inf);

    double x = 1.0 * (b2 * c1 - b1 * c2) / (a1 * b2 - a2 * b1),
           y = 1.0 * (a1 * c2 - a2 * c1) / (a1 * b2 - a2 * b1);
    //printf("%.5lf %.5lf %.5lf %.5lf %.5lf %.5lf\n", a1, b1, c1, a2, b2, c2);
    return mp(x, y);
}

void read()
{
    freopen("camera.in", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i)
        scanf("%lf %lf", &v[0][i].f, &v[0][i].s);
    v[0][n + 1] = v[0][1];
    sg = A(0) > 0 ? 1 : -1;
}
void solve()
{
    int i, j;
    m = 4;
    v[1][1] = mp(-inf, inf);
    v[1][2] = mp(inf, inf);
    v[1][3] = mp(inf, -inf);
    v[1][4] = mp(-inf, -inf);
    v[1][5] = mp(-inf, inf);
    for (i = 1; i <= n; ++ i)
    {
        p = 0;
        if (m <= 2)
        {
            ans = 0.0;
            return ;
        }
        for (j = 1; j <= m; ++ j)
        {
            int k = j + 1;
            int sg1 = sign(v[0][i], v[0][i + 1], v[1][j]),
                sg2 = sign(v[0][i], v[0][i + 1], v[1][k]);

            if (sg1 == sg && sg2 != sg)
            {
                v[2][++ p] = inters(v[0][i], v[0][i + 1], v[1][j], v[1][k]);
                //printf("1 %.5lf %.5lf\n", v[2][p].f, v[2][p].s);
            }
            if (sg1 == sg && sg2 == sg)
            {
                v[2][++ p] = v[1][k];
                //printf("2 %.5lf %.5lf\n", v[2][p].f, v[2][p].s);
            }

            if (sg1 != sg && sg2 == sg)
            {
                v[2][++ p] = inters(v[0][i], v[0][i + 1], v[1][j], v[1][k]);
                v[2][++ p] = v[1][k];
                //printf("3 %.5lf %.5lf\n", v[2][p].f, v[2][p].s);
                //printf("3 %.5lf %.5lf\n", v[2][p - 1].f, v[2][p - 1].s);
            }
            if (p > 1 && (fabs(v[2][p - 1].f - Inf) < e || fabs(v[2][p - 1].s - Inf) < e))
            {
                swap(v[2][p - 1], v[2][p]);
                -- p;
            }
            if (p > 0 && (fabs(v[2][p].f - Inf) < e || fabs(v[2][p].s - Inf) < e))
                -- p;
        }

        copy21();
    }

    ans = A(1);
}
void write()
{
    freopen("camera.out", "w", stdout);
    printf("%.2lf", fabs(ans));
}
int main()
{
    read();
    solve();
    write();
    return 0;
}