Cod sursa(job #1160651)

Utilizator PatrikStepan Patrik Patrik Data 30 martie 2014 18:05:53
Problema Camera Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 kb
    #include<cstdio>
    #include<vector>
    #include<algorithm>
    using namespace std;
    #define NMAX 20001
    #define INF 1000000
    #define pb push_back
    int N,k1,k2;
    struct punct
    {double x , y;}P[NMAX] ,pol1[4*NMAX] , pol2[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;
        return 1;
    }

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