Cod sursa(job #1160530)

Utilizator PatrikStepan Patrik Patrik Data 30 martie 2014 16:51:32
Problema Camera Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.25 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;}P1[NMAX],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;
    }

    punct intersect(punct p1 ,punct p2 , punct p3 , punct p4 )
    {
        punct p;
        double a1 , b1 , c1 , a2 , b2 , c2 ;
        a1 = p2.y-p1.y; a2 = p4.y-p3.y;
        b1 = p1.x-p2.x; b2 = p3.x-p4.x;
        c1 = p1.y*p2.x-p1.x*p2.y; c2 = p3.y*p4.x-p3.x*p4.y;
        if(a1 == 0)
        {
            p.y = p1.y;
            if(b2 == 0)p.x = p3.x;
            else p.x = (-c2-b2*p.y)/a2;
        }
        else
        if(b1 == 0)
        {
            p.x = p1.x;
            if(a2 == 0)p.y = p3.y;
            else p.y = (-c2-a2*p.x)/b2;
        }
        else
        {
            if(a2 == 0)p.y = p3.y , p.x = (-c1-b1*p.y)/a1;
            else if(b2 == 0)p.x = p3.x, p.y = (-c1-a1*p.x)/b1;
            else
            {
                p.x = (b1*c2-b2*c1)/(a1*b2-a2*b1);
                p.y = (-c1-a1*p.x)/b1;
            }
        }
        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" , &P1[i].x , &P1[i].y );
        P1[N+1] = P1[1];
        for(int i = 1 ; i <= N ; ++i )
            A+=det(P1[0],P1[i],P1[i+1]);
        for(int i = 1 ; i <= N ; ++i )
            if(A < 0)P[i] = P1[N-i+1];
            else P[i] = P1[i];
        P[N+1] = P[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 ;
        for(int i = 1 ; i <= N ; ++i )
        {
            sz[l] = 0;
            for(int j = 1 ; j <= sz[1-l] ; ++j )
                {
                    punct p1 = sol[1-l][j] , p2 = sol[1-l][j+1];
                    float d1 = det(P[i],P[i+1],sol[1-l][j]) , d2 = det(P[i],P[i+1],sol[1-l][j+1]) ;
                    if(d1 < 0)
                    {
                        if(d2 < 0)continue;
                        sol[l][++sz[l]] = intersect(P[i],P[i+1],sol[1-l][j],sol[1-l][j+1]);
                        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(P[i],P[i+1],sol[1-l][j],sol[1-l][j+1]);
                    }
                }
            sol[l][sz[l]+1] = sol[l][1];
            /*for(int i = 1 ; i<= sz[l] ; ++i )
                printf("%.2lf %.2lf\n" , sol[l][i].x , sol[l][i].y);
            printf("\n");*/
            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;
    }