Cod sursa(job #1666504)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 28 martie 2016 03:35:30
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.01 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
#define INF 1000000000000000LL
using namespace std;
struct pct{
    long long x;
    long long y;
    long long p;
}v[300],x[300],y[300],z[300],aa,bb,cc;
long long n,i,j,k,a,b,c,nx,ny,nr,ok,p,u,w[300],q[300],sol[300];
long long vmin,l,r,s;
FILE *f,*g;
long long cmp(pct a,pct b){
    if( a.x != b.x )
        return a.x < b.x;
    return a.y < b.y;
}
long long det(pct a,pct b,pct c){
    return 1LL * ( b.x - a.x ) * ( c.y - a.y ) - 1LL * ( c.x - a.x ) * ( b.y - a.y );
}
long long modul(long long a){
    if(a<0)
        return -a;
    return a;
}
long long pg(pct x[],long long m){
    aa = x[1];
    bb = x[m];
    p = 0;
    u = m + 1;
    for(long long i=1;i<=m;i++){
        if( i < m && x[i].y == x[ i + 1 ].y && det( aa, bb, x[i] ) * det( aa, bb, x[ i + 1 ] ) > 0  ){
            return INF;
        }
        if( det( aa, x[i], bb ) >= 0 )
            z[ ++p ] = x[i];
        else
            z[ --u ] = x[i];
    }
    z[ m + 1 ] = z[1];
    z[ m + 2 ] = z[2];
    for(long long i=1;i<=m;i++){
        if( det( z[i], z[ i + 1 ], z[ i + 2 ] ) < 0 )
            return INF;
    }
    long long s = 0;
    for(long long i=1;i<=m-1;i++){
        s +=  det( cc , z[ i ], z[ i + 1 ] ) ;
    }
    return modul(s);
}
int main(){
    f=fopen("gradina.in","r");
    g=fopen("gradina.out","w");
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++){
        fscanf(f,"%d%d",&v[i].x,&v[i].y);
        v[i].p = i;
    }
    cc.x = cc.y = 0;
    sort(v+1,v+n+1,cmp);
    vmin = INF;
    for(i=1;i<=n;i++){
        for(j=i+1;j<=n;j++){
            if( i != j ){
                nx = ny = 0;
                aa = v[i];
                bb = v[j];
                for(k=1;k<=300;k++){
                    x[k].x = x[k].y = x[k].p = y[k].x = y[k].y = y[k].p = 0;
                }
                for(k=1;k<=n;k++) {
                    if ( k == i ){
                        x[ ++nx ] = v[k];
                        q[ v[k].p ] = 1;
                    }
                    else if ( k == j ){
                        y[ ++ny ] = v[k];
                        q[ v[k].p ] = 2;
                    }
                    else if( det( v[k], aa, bb) < 0 ){
                        x[ ++nx ] = v[k];
                        q[ v[k].p ] = 1;
                    }
                    else{
                        y[ ++ny ] = v[k];
                        q[ v[k].p ] = 2;
                    }
                }
                if( nx >= 3 && ny >= 3 ){
                    l = pg(x,nx);
                    r = pg(y,ny);
                    if( l != INF && r != INF  ){
                        if( modul( l - r ) < vmin ){
                            vmin = modul( l - r );
                            for(k=1;k<=n;k++){
                                sol[k] = q[k];
                            }
                        }
                        else if( modul( l - r ) == vmin ){
                            ok = 0;
                            for(k=1;k<=n;k++){
                                if( q[k] < sol[k] ){
                                    ok = 1;
                                    break;
                                }
                                if( sol[k] < q[k] ){
                                    ok = 0;
                                    break;
                                }
                            }
                            if( ok ){
                                for(k=1;k<=n;k++){
                                    sol[k] = q[k];
                                }
                            }
                        }
                    }
                }
                nx = ny = 0;
                for(k=1;k<=300;k++){
                    x[k].x = x[k].y = x[k].p = y[k].x = y[k].y = y[k].p = 0;
                }
                for(k=1;k<=n;k++) {
                    if ( k == j ){
                        x[ ++nx ] = v[k];
                        q[ v[k].p ] = 1;
                    }
                    else if ( k == i ){
                        y[ ++ny ] = v[k];
                        q[ v[k].p ] = 2;
                    }
                    else if( det( v[k], aa, bb) < 0 ){
                        x[ ++nx ] = v[k];
                        q[ v[k].p ] = 1;
                    }
                    else{
                        y[ ++ny ] = v[k];
                        q[ v[k].p ] = 2;
                    }
                }
                if( nx >= 3 && ny >= 3 ){
                    l = pg(x,nx);
                    r = pg(y,ny);
                    if( l != INF && r != INF  ){
                        if( modul( l - r ) < vmin ){
                            vmin = modul( l - r );
                            for(k=1;k<=n;k++){
                                sol[k] = q[k];
                            }
                        }
                        else if( modul( l - r ) == vmin ){
                            ok = 0;
                            for(k=1;k<=n;k++){
                                if( q[k] < sol[k] ){
                                    ok = 1;
                                    break;
                                }
                                if( sol[k] < q[k] ){
                                    ok = 0;
                                    break;
                                }
                            }
                            if( ok ){
                                for(k=1;k<=n;k++){
                                    sol[k] = q[k];
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    fprintf(g,"%lld",vmin/2);
    if( vmin % 2 )
        fprintf(g,".5\n");
    else
        fprintf(g,".0\n");
    for(i=1;i<=n;i++){
        if( sol[i] == 1 )
            fprintf(g,"I");
        else
            fprintf(g,"V");
    }



    fclose(f);
    fclose(g);
    return 0;
}