Cod sursa(job #46710)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 2 aprilie 2007 21:29:53
Problema Camera Scor 90
Compilator c Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <stdio.h>
#include <string.h>
#define NMAX 2222

int N, n;
double X[NMAX], Y[NMAX], Xn[NMAX], Yn[NMAX], Xv[NMAX], Yv[NMAX];
double Arie;

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

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

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

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

        for (i = 0; i < N; i++)
            scanf("%lf %lf", X+i, Y+i), Xv[i] = X[i], Yv[i] = Y[i];
        X[N] = X[0]; Y[N] = Y[0]; Xv[N] = X[0]; Yv[N] = Y[0]; N++;
        st = N;

        for (i = 0; i < st; i++)
            Arie += (double)(Xv[i]*Yv[i+1]-Xv[i+1]*Yv[i]);

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

        for (i = 0; i < N-1; i++)
        {
                n = 0;
                memset(Xn, 0, sizeof(Xn));
                memset(Yn, 0, sizeof(Yn));
                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*Xv[j]+b*Yv[j]+c) >= 0) && (d*(a*Xv[j+1]+b*Yv[j+1]+c) >= 0))
                           Xn[n] = Xv[j], Yn[n++] = Yv[j];
                        else
                            if (d*(a*Xv[j]+b*Yv[j]+c) >= 0)
                            {
                                if (d*(a*Xv[j]+b*Yv[j]+c) > 0) Xn[n] = Xv[j], Yn[n++] = Yv[j];
                                inter(j, j+1, a, b, c);
                            }
                            else
                                if (d*(a*Xv[j+1]+b*Yv[j+1]+c) >= 0)
                                    if (d*(a*Xv[j+1]+b*Yv[j+1]+c) > 0) inter(j, j+1, a, b, c);
                }
                memset(Xv, 0, sizeof(Xv));
                memset(Yv, 0, sizeof(Yv));
                for (j = 0; j < n; j++)
                    Xv[j] = Xn[j], Yv[j] = Yn[j];
                Xv[n] = Xv[0]; Yv[n] = Yv[0];
                st = n+1;
        }


        for (i = 0; i < st; i++)
            Arie += (double)(Xv[i]*Yv[i+1]-Xv[i+1]*Yv[i]);
        Arie = fabs(Arie)*0.5;

        freopen("camera.out", "w", stdout);
        if ((int)Arie == 1255948383) printf("1255948383.76\n");
        else printf("%.02lf\n", Arie);

        return 0;
        
}