Cod sursa(job #121193)

Utilizator victorsbVictor Rusu victorsb Data 7 ianuarie 2008 22:44:23
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

#define Nmax 2048
#define INF 1000000
#define pct pair<double, double>
#define x first
#define y second
#define mp make_pair

const double eps = 1.0e-8;

int n, ct1, ct2;
pct p[Nmax], d1[Nmax], d2[Nmax];

void citire()
{
    int i, a, b;
    
    scanf("%d\n", &n);
    for (i = 1; i <= n; ++i)
    {
        scanf("%d %d\n", &a, &b);
        p[i] = mp(a, b);
    }
    p[n + 1] = p[1];
}

pct inter(double a1, double b1, double c1, double a2, double b2, double c2)
{
    return mp( (b2 * c1 - b1 * c2) / (a2 * b1 - a1 * b2), (a1 * c2 - a2 * c1) / (a2 * b1 - a1 * b2));
}

void solve()
{
    int i, j;
    double a1, b1, c1, a2, b2, c2, arie = 0;
    
    for (i = 1; i <= n; ++i)
        arie += p[i].x * p[i + 1].y - p[i + 1].x * p[i].y;
    
    if (arie > 0)
        reverse(p+1, p+n+2);
    
    d1[++ct1] = mp(-INF, -INF);
    d1[++ct1] = mp(-INF, INF);
    d1[++ct1] = mp(INF, INF);
    d1[++ct1] = mp(INF, -INF);
    d1[ct1 + 1] = d1[1];
    
    for (i = 1; i <= n; ++i)
    {
        ct2 = ct1;
        memcpy(d2, d1, sizeof(d1));
        ct1 = 0;
        
        a1 = p[i].y - p[i + 1].y;
        b1 = p[i + 1].x - p[i].x;
        c1 = p[i].x * p[i + 1].y - p[i + 1].x * p[i].y;
        
        for (j = 1; j <= ct2; ++j)
        {
            a2 = d2[j].y - d2[j + 1].y;
            b2 = d2[j + 1].x - d2[j].x;
            c2 = d2[j].x * d2[j + 1].y - d2[j + 1].x * d2[j].y;
            
            if (a1 * d2[j].x + b1 * d2[j].y + c1 < eps)
                if (a1 * d2[j + 1].x + b1 * d2[j + 1].y + c1 < eps)
                    d1[++ct1] = d2[j + 1];
                else
                    d1[++ct1] = inter(a1, b1, c1, a2, b2, c2);
            else
                if (a1 * d2[j + 1].x + b1 * d2[j + 1].y + c1 < eps)
                {
                    d1[++ct1] = inter(a1, b1, c1, a2, b2, c2);
                    d1[++ct1] = d2[j + 1];
                }
        }
        d1[ct1 + 1] = d1[1];
    }
    
    arie = 0;
    for (i = 1; i <= ct1; ++i)
        arie += d1[i].x * d1[i + 1].y - d1[i + 1].x * d1[i].y;
    
    arie /= 2;
    arie = fabs(arie);
    printf("%.2lf\n", arie);
}

int main()
{
    freopen("camera.in", "r", stdin);
    freopen("camera.out", "w", stdout);
    citire();
    solve();
    return 0;
}