Cod sursa(job #1160745)

Utilizator PatrikStepan Patrik Patrik Data 30 martie 2014 19:18:23
Problema Camera Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.52 kb
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    #define NMAX 2001
    #define INF 100000
    int N,k1,k2;
    struct punct {double x,y;}P[NMAX] , pol1[4*NMAX] , pol2[4*NMAX] ;
    double A;

    double det(punct p1 , punct p2)
    {
        return p1.x*p2.y - p1.y*p2.x;
    }

    void coef(punct p1 , punct p2 , double &a , double &b , double &c)
    {
        a = p2.y-p1.y;
        b = p1.x-p2.x;
        c = p1.y*p2.x-p1.x*p2.y;
    }

    bool interior(punct p , double a , double b , double c)
    {
        if(a*p.x + b*p.y + c <= 0)return 1;
        return 0;
    }

    punct intersectie(double a1 , double b1 , double c1 , double a2 , double b2 , double c2)
    {
        punct p;
        p.x = (b1*c2-b2*c1)/(a1*b2-a2*b1);
        p.y = (a1*c2-a2*c1)/(b1*a2-b2*a1);
        return p;
    }

    int main()
    {
        freopen("camera.in" , "r" , stdin );
        freopen("camera.out" , "w" , stdout );
        scanf("%d" , &N );
        for(int i = 1 ; i<= N ; ++i )
            scanf("%lf%lf" , &P[i].x , &P[i].y );
        P[N+1] = P[1];
        for(int i = 1 ; i<= N ; ++i )
            A+=det(P[i],P[i+1]);
        if(A < 0)
        {
            reverse(P+1,P+N+1);
            P[N+1] = P[1];
        }
        punct p;
        p.x = p.y = -INF; pol1[++k1] = p;
        p.x = INF; pol1[++k1] = p;
        p.y = INF; pol1[++k1] = p;
        p.x = -INF; pol1[++k1] = p;
        pol1[5] = pol1[1];
        double a,b,c,a1,b1,c1;
        for(int i = 1 ; i <= N ; ++i )
        {
            coef(P[i],P[i+1],a,b,c);
            for(int j = 1 ; j<= k1 ; ++j )
            {
                coef(pol1[j],pol1[j+1],a1,b1,c1);
                bool s1 = interior(pol1[j],a,b,c);
                bool s2 = interior(pol1[j+1],a,b,c);
                if(s1)
                {
                    if(s2)pol2[++k2] = pol1[j+1];
                    else pol2[++k2] = intersectie(a,b,c,a1,b1,c1);
                }
                else
                    if(s2){
                        pol2[++k2] = intersectie(a,b,c,a1,b1,c1);
                        pol2[++k2] = pol1[j+1];
                    }
            }
            for(int j = 1 ; j <= k2 ; ++j )
                pol1[j] = pol2[j];
            k1 = k2;
            k2 = 0;
            pol1[k1+1] = pol1[1];
        }
        A = 0;
        for(int i = 1 ; i<= k1 ; ++i )
            A += det(pol1[i],pol1[i+1]);
        if(A < 0)A = -A;
        A/=2;
        printf("%.2lf" , A);
        return 0;
    }