Cod sursa(job #1674540)

Utilizator rughibemBelcineanu Alexandru Ioan rughibem Data 4 aprilie 2016 18:41:53
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include<cstdio>
#include<algorithm>
#define DIM 2016
#define EPS 1e-6
#define INF 100000.0
FILE *f=fopen("camera.in","r"), *g=fopen("camera.out","w");

using namespace std;

struct Punct{ double x, y; } v[DIM], A[DIM], A2[DIM], ZERO;

int N, M, M2, sens;

double Det( Punct A, Punct B, Punct C ){

    return A.x * B.y + B.x * C.y + C.x * A.y
         - A.y * B.x - B.y * C.x - C.y * A.x;

}

int Semn( double Q ){

    if( -EPS <= Q && Q <= EPS )
        return 0;
    if( Q > EPS )
        return 1;
        return -1;

}

void Citire(){
int i;
double aria;

    fscanf(f,"%d\n",&N);

    for(i=1;i<=N;i++)
        fscanf(f,"%lf %lf\n",&v[i].x,&v[i].y);
        v[N+1] = v[1];

    ZERO.x = ZERO.y = 0;

    aria = 0.0;
    for(i=1;i<=N;i++)
        aria += Det( ZERO, v[i], v[i+1] );

    if( aria > 0 )
        sens = 1;
    else
        sens = -1;

}

void Initializare(){

    M = 4;
    A[1].x = -INF; A[1].y = -INF;
    A[2].x = INF;  A[2].y = -INF;
    A[3].x = INF;  A[3].y = INF;
    A[4].x = -INF; A[4].y = INF;
    A[5] = A[1];

}

Punct Intersectia( Punct A, Punct B, Punct C, Punct D ){
double a1, b1, c1, a2, b2, c2;
Punct R;

    a1 = B.y - A.y;
    b1 = A.x - B.x;
    c1 = B.x * A.y - A.x * B.y;

    a2 = D.y - C.y;
    b2 = C.x - D.x;
    c2 = D.x * C.y - C.x * D.y;

    if ( Semn( (a1 * b2) - (a2 * b1) ) == 0 )
        R.x = (c2 * b1) - (c1 * b2);
    else
        R.x = ( (c2 * b1) - (c1 * b2) ) / (( a1 * b2) - (a2 * b1) );

    if ( Semn( (a2 * b1) - (a1 * b2) ) == 0 )
        R.y = (a1 * c2) - (a2 * c1);
    else
        R.y = ((a1 * c2) - (a2 * c1)) / ((a2 * b1) - (a1 * b2));

    return R;
}


void Taie( Punct UNU, Punct DOI ){
int i, cur, next, scur, snext;

    M2 = 0;

    for(i=1;i<=M;i++){

        cur  = i;
        next = i+1;

        scur = Semn( Det( UNU, DOI, A[cur] ) );
        snext= Semn( Det( UNU, DOI, A[next] ) );

        if( scur == sens && snext == sens ) // ambele in interior
            A2[++M2] = A[next];

        else if( scur == sens && snext != sens ) // cur interior, next afara
            A2[++M2] = Intersectia( UNU, DOI, A[cur], A[next] );

        else if( scur != sens && snext == sens ){   // cur afara, next int
            A2[++M2] = Intersectia( UNU, DOI, A[cur], A[next] );
            A2[++M2] = A[next];
        }
    }

    M = M2;
    for(i=1;i<=M2;i++)
        A[i] = A2[i];
        A[M+1] = A[1];

}

void CalculeazaSOL(){
double aria = 0.0;
int i;

    for(i=1;i<=M;i++)
        aria += Det( ZERO, A[i], A[i+1] );

    if( aria < 0 )
        aria = -aria;

    fprintf(g,"%.2lf\n",aria / 2.0);
}

int main(){

    Citire();

    Initializare();

    for(int i=1;i<=N;i++)
        Taie( v[i], v[i+1] );

    CalculeazaSOL();

return 0;
}