Cod sursa(job #542295)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 26 februarie 2011 10:15:45
Problema Camera Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <stdio.h>
#define Nmax 2005
#define Max_coord 100000
#define INF 2147000000
#define eps 0.000001

struct punct{
    double x,y;
} P[Nmax],K[2][Nmax];

int N,sz[2];
int X[Nmax],Y[Nmax];

inline double Minim(double x,double y){ return x<y ? x:y; }
inline double Maxim(double x,double y){ return x>y ? x:y; }
inline int cmp0(int q){
    if( q-eps > 0 ) return 1;
    if( q+eps < 0) return -1;
    return 0;
}
inline int Semn(punct p0,punct p1,punct p2){
    double q=(p1.x-p0.x)*(p2.y-p0.y) - (p1.y-p0.y)*(p2.x-p0.x) ;
    return cmp0(q);
}
inline double Prod(punct p1,punct p2){
    return p1.x*p2.y - p2.x*p1.y;
}
inline double Abs(double a){ return a>0 ? a:-a;}
inline int egal( double a,double b){
    if( Abs(a-b) < eps ) return 1;
    return 0;
}
inline punct Intersect(punct a,punct b,punct c,punct d){
    double A1,A2,B1,B2; punct p;
    if( !egal(a.x , b.x ) ) A1=(a.y-b.y)/(a.x-b.x);
    else A1=INF;
    B1=a.y-A1*a.x;

    if( !egal(c.x , d.x ) ) A2=(c.y-d.y)/(c.x-d.x);
    else A2=INF;
    B2=c.y-A2*c.x;

    if( !egal(A1,A2) ) p.x=(B2-B1)/(A1-A2);
    else p.x=INF;
    if( egal( A1,INF )) p.y=A2*p.x+B2;
    else p.y=A1*p.x+B1;
    return p;
}

int main(){
    int i,j,semn=0,s1,s2; double arie=0,minx=INF,miny=INF,maxx=0,maxy=0;
    freopen("camera.in","r",stdin);
    freopen("camera.out","w",stdout);
    scanf("%d",&N);
    for(i=1;i<=N;++i){
        scanf("%lf%lf",&P[i].x,&P[i].y);
        minx=Minim(P[i].x,minx); miny=Minim(P[i].y,miny);
        maxx=Maxim(P[i].x,maxx); maxy=Maxim(P[i].y,maxy);
    }
    P[N+1]=P[1];
    for(i=1;i<=N;++i)
        semn+=Prod(P[i],P[i+1]);
    semn=cmp0(semn);
    semn *= -1;

    K[1][1].x=minx; K[1][1].y=miny;
    K[1][2].x=maxx; K[1][2].y=miny;
    K[1][3].x=maxx; K[1][3].y=maxy;
    K[1][4].x=minx; K[1][4].y=maxy;
    sz[1]=4;

    for(i=1;i<=N;++i){
        sz[(i+1)&1]=0;
        K[i&1][sz[i&1]+1]=K[i&1][1];

        for(j=1;j<=sz[i&1];++j){

            s1=Semn(P[i],P[i+1],K[i&1][j]);
            s2=Semn(P[i],P[i+1],K[i&1][j+1]);
           // printf("%d%d\n",s1,s2);

            if( s1==semn && s2==semn ) continue;
            if( s1!=semn && s2!=semn ){
                K[(i+1)&1][++sz[(i+1)&1]]=K[i&1][j+1];
                continue;
            }
            K[(i+1)&1][++sz[(i+1)&1]]=Intersect(P[i],P[i+1],K[i&1][j],K[i&1][j+1]);
            if( s2!=semn ) K[(i+1)&1][++sz[(i+1)&1]]=K[i&1][j+1];
        }
    }

    N++;
    K[N&1][sz[N&1]+1]=K[N&1][1];
    for(i=1;i<=sz[N&1];++i)
        arie += Prod(K[N&1][i],K[N&1][i+1]);
    arie/=2;
    if( sz[N&1]<3 ) arie=0;
    printf("%.2lf\n",arie);
    fclose(stdin); fclose(stdout);
    return 0;
}