Cod sursa(job #1658945)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 21 martie 2016 21:34:25
Problema Camera Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.05 kb
#include<cstdio>
#include<cmath>
#define EPS 0.0000001
#define INF 1111111
struct pct{
    double x;
    double y;
}v[2100],x[2100],y[2100],ze,pp;
int n,i,j,nr,np,ok;
double a,xmax,xmin,ymax,ymin;
FILE *f,*g;
double ar(pct a,pct b,pct c){
    return a.x * ( b.y - c.y ) + b.x * ( c.y - a.y ) + c.x * ( a.y - b.y );
}
double ec(pct a,pct b,pct c){
    return c.x * ( a.y - b.y ) + c.y *( b.x - a.x ) + a.x * b.y - a.y * b.x;
}
void intc(pct &r,pct a,pct b,pct c,pct d){
    r.x = ( ( b.x - a.x ) * ( c.x * d.y - c.y * d.x ) - ( a.x * b.y - a.y * b.x ) * ( d.x - c.x ) ) /  ( ( d.x - c.x ) * ( a.y - b.y ) - ( c.y - d.y ) * ( b.x - a.x ) );
    if( b.x - a.x != 0 )
        r.y = ( a.y * b.x - a.x * b.y - r.x * ( a.y - b.y ) ) / ( b.x - a.x );
    else
        r.y = ( c.y * d.x - c.x * d.y - r.x * ( c.y - d.y ) ) / ( d.x - c.x );
}
double maxim(double a,double b){
    if( a > b )
        return a;
    return b;
}
double minim(double a,double b){
    if( a < b )
        return a;
    return b;
}
double modul(double a){
    if( a < 0 )
        return -a;
    return a;
}
int dif(pct a,pct b){
    if( a.x - b.x <= EPS && a.x - b.x >= -EPS )
        if( a.y - b.y <= EPS && a.y - b.y >= -EPS )
            return 1;
    return 0;
}
void fct(int p,double arie){
    double s;
    s = ec( v[p], v[ p + 1 ], v[ p - 1 ] );
    if( ar( v[ p - 1 ] , v[p] , v[ p + 1 ] ) * arie < 0 )
        s = -s;
    np = 0;
    ok = 0;
    x[nr] = x[0];
    for(int i=0;i<=nr;i++){
        if( ec( v[p] , v[ p + 1 ], x[i] ) * s >= 0 ){
            if( !ok ){
                np++;
                intc( y[np] , v[p] , v[ p + 1 ], pp , x[i] );
            }
            if( i != nr && !( j > 0 && dif( y[np] , x[i] ) ) ){
                y[ ++np ] = x[i];
                ok = 1;
            }
        }
        else{
            if( ok ){
                intc( y[np] , v[p] , v[ p + 1 ], pp, x[i] );
                if( !( j > 0 && dif( y[np] , y[ np - 1 ] ) ) )
                    np++;
            }
            ok=0;
        }
        pp = x[i];
    }
    for(int i=0;i<np;i++){
        x[i] = y[i];
    }
    nr = np;
}
int main(){
    f=fopen("camera.in","r");
    g=fopen("camera.out","w");
    fscanf(f,"%d",&n);
    xmax = ymax = -INF;
    xmin = ymin = INF;
    for(i=0;i<n;i++){
        fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
        xmax = maxim( xmax, v[i].x );
        xmin = minim( xmin, v[i].x );
        ymax = maxim( ymax, v[i].y );
        ymin = minim( ymin, v[i].y );
    }
    v[n] = v[0];
    v[n+1] = v[1];
    ze.x = ze.y = 0;
    for(i=0;i<n;i++){
        a += ar( ze, v[i], v[ i + 1 ] );
    }
    x[0].x = xmin;
    x[0].y = ymin;
    x[1].x = xmax;
    x[1].y = ymin;
    x[2].x = xmin;
    x[2].y = ymax;
    x[3].x = xmax;
    x[3].y = ymax;
    nr = 4;
    for(i=0;i<n;i++){
        fct(i+1,a);
    }
    x[nr] = x[0];
    a = 0;
    for(i=0;i<nr;i++){
        a += ar( ze, x[i], x[i + 1 ] );
    }
    a = modul( a / 2 );
    fprintf(g,"%.2lf",a);
    fclose(f);
    fclose(g);
    return 0;
}