Cod sursa(job #1160595)

Utilizator PatrikStepan Patrik Patrik Data 30 martie 2014 17:35:48
Problema Camera Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.74 kb
    #include<cstdio>
    #include<vector>
    #include<algorithm>
    using namespace std;
    #define NMAX 20001
    #define INF 1000000
    #define pb push_back
    int N,sz[2];
    struct punct
    {double x , y;}P[NMAX] ,sol[2][4*NMAX];
    float A;

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

    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;
    }

    punct intersect(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 semn(double a , double b , double c , punct p)
    {
        if(a*p.x+b*p.y+c > 0)return -1;
        if(a*p.x+b*p.y+c < 0)return 1;
        return 0;
    }

    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[0],P[i],P[i+1]);
        if(A < 0)reverse(P+1,P+N+1);
        punct p;
        p.x = -INF,p.y = -INF;sol[0][1] = p;
        p.x = INF;sol[0][2] = p;
        p.y = INF;sol[0][3] = p;
        p.x =-INF;sol[0][4] = p;
        sol[0][5] = sol[0][1];
        sz[0] = 4;
        int l = 1 ;
        double a,b,c,a1,b1,c1;
        for(int i = 1 ; i <= N ; ++i )
        {
            sz[l] = 0;
            coef(P[i],P[i+1],a,b,c);
            for(int j = 1 ; j <= sz[1-l] ; ++j )
                {
                    punct p1 = sol[1-l][j] , p2 = sol[1-l][j+1];
                    int d1 = semn(a,b,c,sol[1-l][j]) , d2 = semn(a,b,c,sol[1-l][j+1]) ;
                    coef(sol[1-l][j],sol[1-l][j+1],a1,b1,c1);
                    if(d1 < 0)
                    {
                        if(d2 < 0)continue;
                        sol[l][++sz[l]] = intersect(a,b,c,a1,b1,c1);
                        sol[l][++sz[l]] = sol[1-l][j+1];
                    }
                    else
                    {
                        if(d2 >= 0)sol[l][++sz[l]] = sol[1-l][j+1];
                        else sol[l][++sz[l]] = intersect(a,b,c,a1,b1,c1);
                    }
                }
            sol[l][sz[l]+1] = sol[l][1];
            l = 1-l;
        }
        A = 0;
        for(int i = 1 ; i<= sz[1-l] ; ++i )
            A+=det(P[0],sol[1-l][i],sol[1-l][i+1]);
        if(A < 0)A = -A;
        A/=2;
        printf("%.2f" , A);
        return 0;
    }