Cod sursa(job #111847)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 1 decembrie 2007 23:47:01
Problema Camera Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.3 kb
#include <cstdio>
#include <cstring>
#include <cmath>
#define NKAX 5050
#define eps 1e-9

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

void read()
{
        int i;
        double maxy = -666000666, maxx = -666000666, 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]);
            //Xk[K] = X[i]; Yk[K++] = Y[i];
            minx = ( ((minx-X[i])>eps)? X[i]:minx );
            maxx = ( ((maxx-X[i])<eps)? X[i]:maxx );
            maxy = ( ((maxy-Y[i])<eps)? Y[i]:maxy );
            miny = ( ((miny-Y[i])>eps)? Y[i]:miny );
        }

        //Xk[K] = X[0]; Yk[K++] = Y[0];
        X[N] = X[0]; Y[N++] = Y[0];
        //maxy += 1000;
        Xk[K] = minx; Yk[K++] = miny;
        Xk[K] = maxx; Yk[K++] = miny;
        Xk[K] = maxx; Yk[K++] = maxy;
        Xk[K] = minx; Yk[K++] = maxy;
        Xk[K] = minx; Yk[K++] = miny;
}

void inter(int i, int j, double a, double b, double c)
{
        double a1 = Yk[i]-Yk[j], b1 = Xk[j]-Xk[i], c1 = Xk[i]*Yk[j]-Xk[j]*Yk[i];

        tX[n] = (b*c1-b1*c)/(a*b1-b*a1);
        tY[n++] = (c1*a-c*a1)/(a1*b-b1*a);
}

void old()
{
        int i, j, st, d;
        double a, b, c;

        for (i = 0; i < N; i++)
            Xk[i] = X[i], Yk[i] = Y[i];
        X[N] = X[0]; Y[N] = Y[0]; Xk[N] = X[0]; Yk[N] = Y[0]; N++;
        st = N;

        for (i = 0; i < st; i++)
            Ans += (double)(Xk[i]*Yk[i+1]-Xk[i+1]*Yk[i]);

        d = 1;
        if (Ans <= 0) d = -1;
        Ans = 0;

        for (i = 0; i < N-1; i++)
        {
                n = 0;
                memset(tX, 0, sizeof(tX));
                memset(tY, 0, sizeof(tY));
                a = Y[i]-Y[i+1];
                b = X[i+1]-X[i];
                c = X[i]*Y[i+1]-X[i+1]*Y[i];
                for (j = 0; j < st-1; j++)
                {
                        if ((d*(a*Xk[j]+b*Yk[j]+c) >= 0) && (d*(a*Xk[j+1]+b*Yk[j+1]+c) >= 0))
                           tX[n] = Xk[j], tY[n++] = Yk[j];
                        else
                            if (d*(a*Xk[j]+b*Yk[j]+c) >= 0)
                            {
                                if (d*(a*Xk[j]+b*Yk[j]+c) > 0) tX[n] = Xk[j], tY[n++] = Yk[j];
                                inter(j, j+1, a, b, c);
                            }
                            else
                                if (d*(a*Xk[j+1]+b*Yk[j+1]+c) > 0) inter(j, j+1, a, b, c);
                }
                memset(Xk, 0, sizeof(Xk));
                memset(Yk, 0, sizeof(Yk));
                for (j = 0; j < n; j++)
                    Xk[j] = tX[j], Yk[j] = tY[j];
                Xk[n] = Xk[0]; Yk[n] = Yk[0];
                st = n+1;
        }
}

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 += (double)(X[i]*Y[i+1]-X[i+1]*Y[i]);

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

        for (i = 0; i < N; i++)
        {
                n = 0;
                memset(tX, 0, sizeof(tX));
                memset(tY, 0, sizeof(tY));
                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);
                                //inter(j, j+1, a, b, c);
                            }
                            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);
                                    //inter(j, j+1, a, b, c);
                                }
                }
                if (n>2) {memset(Xk, 0, sizeof(Xk));
                memset(Yk, 0, sizeof(Yk));
                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();
        if (N<20) old();
	else solve();
        write();
        return 0;
}