Cod sursa(job #111503)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 30 noiembrie 2007 09:27:26
Problema Camera Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.09 kb
#include <cstdio>
#include <cstring>
#include <cmath>
#define NKAX 5050
#define eps 1e-10

int N, K;
double X[NKAX], Y[NKAX], Xk[NKAX], Yk[NKAX], tX[NKAX], tY[NKAX], Ans;

void read()
{
        int i;
        double maxy = 0, maxx = 0, minx = 666000666, miny = 666000666;

        freopen("camera.in", "r", stdin);
        scanf("%d", &N);

        for (i = 0; i < N; i++) {
            scanf("%lf %lf", &X[i], &Y[i]);
            minx = ( ((minx-Y[i])>eps)? Y[i]:minx );
            maxx = ( ((maxx-Y[i])<eps)? Y[i]:maxx );
            maxy = ( ((maxy-Y[i])<eps)? Y[i]:maxy );
            miny = ( ((miny-Y[i])>eps)? Y[i]:miny );
        }

        //maxy += 1000;
        Yk[K] = miny; Xk[K++] = minx;
        Yk[K] = miny; Xk[K++] = maxx;
        Xk[K] = maxx; Yk[K++] = maxy;
        Xk[K] = minx; Yk[K++] = maxy;
        Yk[K] = miny; Xk[K++] = minx;
}

void kernel()
{
        int i, j, n = 0, d = 1;
        double a, b, c, a1, b1, c1, xi, yi, arie=0;

        N--;
        for (i = 0; i < N; i++)
            arie += (X[i]*Y[i+1]-X[i+1]*Y[i]);

        d = 1;
        if (arie<-eps) d = -1;

        for (i = 0; i < N; i++)
        {
                for (j = 0; j < n; j++) tX[j] = tY[j] = 0;
                n = 0;
                a = Y[i]-Y[i+1]; b = X[i+1]-X[i]; c = X[i]*Y[i+1]-X[i+1]*Y[i];
                K--;
                for (j = 0; j < K; j++)
                {
                        if ( (d*((a*Xk[j]+b*Yk[j]+c)) >= -eps)&&( (d*(a*Xk[j+1]+b*Yk[j+1]+c)) >= -eps) )
                           tX[n] = Xk[j], tY[n++] = Yk[j];
                        else
                            if (d*((a*Xk[j]+b*Yk[j]+c)) >= -eps)
                            {
                                if (d*((a*Xk[j]+b*Yk[j]+c)) > eps) tX[n] = Xk[j], tY[n++] = Yk[j];
                                a1 = Yk[j]-Yk[j+1]; b1 = Xk[j+1]-Xk[j]; c1 = Xk[j]*Yk[j+1]-Xk[j+1]*Yk[j];
                                tX[n] = (b*c1-b1*c)/(a*b1-b*a1);
                                tY[n++] = (c1*a-c*a1)/(a1*b-b1*a);
                            }
                            else
                                if ((d*(a*Xk[j+1]+b*Yk[j+1]+c)) > eps)
                                {
                                     a1 = Yk[j]-Yk[j+1]; b1 = Xk[j+1]-Xk[j], c1 = Xk[j]*Yk[j+1]-Xk[j+1]*Yk[j];
                                     tX[n] = (b*c1-b1*c)/(a*b1-b*a1);
                                     tY[n++] = (c1*a-c*a1)/(a1*b-b1*a);
                                }

                }
                for (j = 0; j < n; j++)
                    Xk[j] = tX[j], Yk[j] = tY[j];
                Xk[n] = Xk[0]; Yk[n] = Yk[0];
                K = n+1;
        }

}

void solve()
{
        int i;
        kernel();
        K--;
        Ans = 0;
        for (i = 0; i < K; i++)
            Ans += (Xk[i]*Yk[i+1]-Xk[i+1]*Yk[i]);
        if (Ans<eps) Ans = -Ans;
        Ans = 0.5*Ans;
}

void write()
{
        freopen("camera.out", "w", stdout);
        printf("%0.2lf\n", Ans);
}

int main()
{
        read();
        solve();
        write();
        return 0;
}