Cod sursa(job #1666495)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 28 martie 2016 02:46:28
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.11 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
#define INF 1000000000000000LL
using namespace std;
struct pct{
    int x;
    int y;
    int p;
}v[300],x[300],y[300],aa,bb,cc;
int n,i,j,k,a,b,c,nx,ny,nr,ok,z[300],w[300],q[300],sol[300];
long long vmin,l,r,s;
FILE *f,*g;
int 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 ( b.x - a.x ) * ( c.y - a.y ) - ( 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[],int m){
    for(i=1;i<=300;i++){
        z[i] = w[i] = 0;
    }
    nr = 2;
    w[1] = z[2] = 1;
    w[2] = 2;
    for(int i=3;i<=m;i++){
        if( z[i] != 1 ){
            while( nr >= 2 && det( x[ w[ nr - 1 ] ] , x[ w[nr] ] , x[i] ) < 0 ){
                z[ w[nr] ] = 0;
                nr--;
            }
            z[i] = 1;
            nr++;
            w[nr] = i;
        }
    }
    for(int i=m;i>=1;i--){
        if( z[i] != 1 ){
            while( nr >= 2 && det( x[ w[ nr - 1 ] ] , x[ w[nr] ] , x[i] ) < 0 ){
                z[ w[nr] ] = 0;
                nr--;
            }
            z[i] = 1;
            nr++;
            w[nr] = i;
        }
    }
    if( nr != m+1 )
        return INF;
    long long s = 0;
    for(int i=1;i<n-1;i++){
        s += modul( det( x[ w[i] ] , x[ w[ i + 1 ] ] , x[ w[ i + 2 ] ] ) );
    }
    return 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;
    }
    sort(v+1,v+n+1,cmp);
    vmin = INF;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if( i != j ){
                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( i == k ){
                        x[ ++ nx ] = v[k];
                        q[ v[k].p ] = 1;
                    }
                    else if( j == k ){
                        y[ ++ ny ] = v[k];
                        q[ v[k].p ] = 2;
                    }
                    else if( det( v[i] , v[j] , v[k] ) < 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;
}