Cod sursa(job #164210)

Utilizator FlorinC1996Florin C FlorinC1996 Data 23 martie 2008 17:54:29
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 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;   
}