Cod sursa(job #116395)

Utilizator mariusdrgdragus marius mariusdrg Data 18 decembrie 2007 15:50:39
Problema Camera Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.62 kb
#include<stdio.h>

const int maxn = 10100;

int n;
int i;
int j;
 double x[maxn];
 double y[maxn];
 double colx[maxn];
 double coly[maxn];
 double colx1[maxn];
 double coly1[maxn];
int l;
int l1;
 double sol;

 double xg,yg;

 double abs( double x)
{
        if (x < 0) return x * -1;
        return x;
}

 double arie( double x1, double y1, double x2, double y2, double x3, double y3)
{
        return x1 * y2 + x2 * y3 + x3 * y1 - y1 * x2 - y2 * x3 - y3 * x1;
}

int main()
{
        #ifndef ONLINE_JUDGE
        freopen("camera.in","r",stdin);
        freopen("camera.out","w",stdout);
        #endif
        int nrt = 1;
        //scanf("%d",&nrt);
        for(;nrt;--nrt)
        {

        scanf("%d",&n);
        for(i = 1;i <= n; ++i)
        {
                scanf("%lf %lf",&x[i],&y[i]);
        }

        x[n + 1] = x[1];
        y[n + 1] = y[1];
        x[n + 2] = x[2];
        y[n + 2] = y[2];
        colx[1] = -100000;
        coly[1] = -100000;
        colx[2] =  100000;
        coly[2] = -100000;
        colx[3] =  100000;
        coly[3] =  100000;
        colx[4] = -100000;
        coly[4] =  100000;
        colx[5] = -100000;
        coly[5] = -100000;

        l = 4;

         for(j = 1;j <= n; ++j)
         {
                xg += x[j];
                yg += y[j];
         }

         xg /= n;
         yg /= n;

        for(i = 1;i <= n; ++i)
        {

                for(j = 1;j <= l;++j)
                {
                         double a = y[i + 1] - y[i];
                         double b = x[i] - x[i + 1];
                         double c = x[i] * y[i + 1] -  x[i + 1] * y[i];
                         double a1 = coly[j + 1] - coly[j];
                         double b1 = colx[j] - colx[j + 1];
                         double c1 = coly[j + 1] * colx[j] - coly[j] * colx[j + 1];
                         double y1 = (c1 * a - a1 * c) / (b1 * a - b * a1);
                         double x1 = (c - b * y1) / a;
                         if (a == 0)
                         {
                                x1 = (c1 - b1 * y1) / a1;
                         }
                         if ( b1 * a - b * a1 == 0 )
                         {
                                x1 = x[i + 1];
                                y1 = y[i + 1];
                         }
                         double ver = arie(x[i],y[i],x[i + 1],y[i + 1],xg,yg);

                        if (((arie(x[i], y[i], x[i + 1],y[i + 1], colx[j],coly[j]) < 0) == (ver < 0) ) && ((arie(x[i], y[i], x[i + 1],y[i + 1], colx[j + 1],coly[j + 1]) < 0) == (ver < 0)))
                        {
                                ++l1;
                                colx1[l1] = colx[j + 1];
                                coly1[l1] = coly[j + 1];
                        }
                        if (((arie(x[i], y[i], x[i + 1],y[i + 1], colx[j],coly[j]) < 0) != (ver < 0) ) && ((arie(x[i], y[i], x[i + 1],y[i + 1], colx[j + 1],coly[j + 1]) < 0) == (ver < 0)))
                        {
                                ++l1;
                                colx1[l1] = x1;
                                coly1[l1] = y1;
                                if (x1 != colx[j + 1] || y1 != coly[j + 1])
                                {
                                        ++l1;
                                        colx1[l1] = colx[j + 1];
                                        coly1[l1] = coly[j + 1];
                                }
                        }
                        if (((arie(x[i], y[i], x[i + 1],y[i + 1], colx[j],coly[j]) < 0) != (ver < 0) ) && ((arie(x[i], y[i], x[i + 1],y[i + 1], colx[j + 1],coly[j + 1]) < 0) != (ver < 0)))
                        {
                                continue;
                        }
                        if (((arie(x[i], y[i], x[i + 1],y[i + 1], colx[j],coly[j]) < 0) == (ver < 0) ) && ((arie(x[i], y[i], x[i + 1],y[i + 1], colx[j + 1],coly[j + 1]) < 0) != (ver < 0)))
                        {
                                ++l1;
                                colx1[l1] = x1;
                                coly1[l1] = y1;
                        }
                }
                l = l1;
                for(j = 1;j <= l1; ++j)
                {
                        colx[j] = colx1[j];
                        coly[j] = coly1[j];
                        colx1[j] = 0;
                        coly1[j] = 0;
                }
                l1 = 0;
                colx[l + 1] = colx[1];
                coly[l + 1] = coly[1];
        }

        for(i = 1;i <= l; ++i)
        {
                sol += colx[i] * coly[i + 1] - coly[i] * colx[i + 1];
        }
        
        printf("%.2lf\n",abs(sol) / 2);
        }
        return 0;
}