Cod sursa(job #116583)

Utilizator mariusdrgdragus marius mariusdrg Data 18 decembrie 2007 23:28:05
Problema Camera Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.92 kb
#include<stdio.h>

#include<algorithm>


using namespace std;

const int maxn = 10100;

struct xy
{
        double x1,y1;
};

int n;
int i;
int j;
double x[maxn];
double y[maxn];
double colx[maxn];
double coly[maxn];
double colx1[maxn];
double saux[maxn];
double coly1[maxn];
int l;
int l1;
 double sol;
 xy a[maxn];
int viz[maxn];
int st[maxn];
 double xg,yg;

 bool cmpf(xy i,xy j)
 {
        return (i.x1 < j.x1) || (i.x1 == j.x1 && i.y1 < j.y1);
 }

 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]);
                a[i].x1 = x[i];
                a[i].y1 = y[i];
        }

        if (arie(x[1],y[1],x[2],y[2],x[3],y[3]) < 0)
        {
                memcpy(saux,x,sizeof(x));
                for(i = 1;i <= n; ++i)
                {
                        x[i] = saux[n - i + 1];
                }
                memcpy(saux,y,sizeof(y));
                for(i = 1;i <= n; ++i)
                {
                        y[i] = saux[n - i + 1];
                }
        }

        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;
         
         sort(a + 1, a + n + 1,cmpf);
         int p = 1;
         st[ st[0] = 1 ] = 1;
         for (i = 1; i >= 1; i += ( p = (i == n) ? -p : p ) ) {
         if (viz[i]) continue;
         while (st[0] >= 2 && arie(a[ st[ st[0] - 1] ].x1,a[st[st[0] - 1]].y1, a[ st[ st[0] ] ].x1,a[st[st[0]]].y1, a[i].x1,a[i].y1) < 0) viz[ st[ st[0]-- ] ] = 0;
         viz[ st[ ++st[0] ] = i ] = 1;
         }

         for(j = 1;j <= n; ++j)
         {
                xg += a[j].x1;
                yg += a[j].y1;
         }

         if (st[0] >= n) st[0] = 0;

         for(j = 1;j <= st[0]; ++j)
         {
                xg -= a[st[j]].x1;
                yg -= a[st[j]].y1;
         }

         xg /= (n - st[0]);
         yg /= (n - st[0]);

        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);
                   //     double ver = 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] = 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;
}