Cod sursa(job #1672515)

Utilizator rughibemBelcineanu Alexandru Ioan rughibem Data 2 aprilie 2016 20:15:35
Problema Gradina Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.72 kb
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<deque>
#define lli long long int
#define DIM 252
#define INF 10000000000000000
FILE *f=fopen("gradina.in","r"), *g=fopen("gradina.out","w");

using namespace std;

struct Punct{ int x, y, ind; } v[DIM], ZERO;

vector <int>  UNU,  DOI;
deque  <int> rUNU, rDOI;    // reordonat

int N;
lli DIF = INF;
bool SOL[DIM], sol[DIM];

bool cmp( Punct A, Punct B ){

    if( A.x < B.x || ( A.x == B.x && A.y < B.y ) )
        return 1; return 0;
}

void Citire(){
int i;

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

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

        fscanf(f,"%d %d\n",&v[i].x,&v[i].y);

        v[i].ind = i;

    }   sort(v+1,v+N+1,cmp);

    ZERO.x = ZERO.y = 0;

}

lli 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 );
}

void CreareUNUDOI( int i, int j ){
int k;

    UNU.clear(); rUNU.clear();
    DOI.clear(); rDOI.clear();

    UNU.push_back(i);
    DOI.push_back(j);

    for(k=1;k<=N;k++)
        if( i != k && k != j ){
            if( det( v[i], v[j], v[k] ) < 0 )
                UNU.push_back(k);
            else
                DOI.push_back(k);
        }

}

void Reordonare( vector <int> OOO, deque <int> &rOOO ){
int i, lp;

    lp = OOO.size(); // nr elemente din OOO

    rOOO.push_back( OOO[0] );

    for(i=1;i<=lp-2;i++){

        if( det( v[ OOO[0] ], v[ OOO[lp-1] ], v[ OOO[i] ] ) > 0 )
            rOOO.push_back( OOO[i] );
        else
            rOOO.push_front( OOO[i] );

    }

    rOOO.push_back( OOO[lp-1] );
    rOOO.push_back( rOOO.front() );
    rOOO.push_back( rOOO[1] );

}

bool ePolig( deque <int> P ){
int i, lp = P.size(); // nr elemente

    for(i=0;i<=lp-3;i++)
        if( det( v[ P[i] ], v[ P[i+1] ], v[ P[i+2] ] ) > 0 )
            return 0;

    return 1;

}

lli Modul( lli OOO ){ if( OOO < 0 ) return -OOO; return OOO; }

lli Aria( deque <int> P ){
lli aria = 0;
int i;

    for(i=0;i<=P.size()-2-1;i++)
        aria += det( ZERO, v[ P[i] ], v[ P[i+1] ] );

    return Modul(aria);
}

void Configuratie(){
int i;

    memset(sol,0,sizeof(sol));

    for(i=0;i<=rUNU.size()-2;i++)
        sol[ v[ rUNU[i] ].ind ] = 1;

    if( sol[1] == 1 )
        for(i=1;i<=N;i++)
            sol[i] = ( sol[i] + 1 ) % 2;

}

bool Comp(){
int i;

    for(i=1;i<=N;i++){
        if( sol[i] == 0 && SOL[i] == 1 )
            return 1;
        else if( sol[i] == 1 && SOL[i] == 0 )
            return 0;
    }

    return 0;
}

void Afisare(){
int o;

    fprintf(g,"%lld",DIF/2);
    if( DIF % 2 == 0 )
        fprintf(g,".0\n");
    else
        fprintf(g,".5\n");

    for(o=1;o<=N;o++)
        if( SOL[o] == 0 )
            fprintf(g,"I");
        else
            fprintf(g,"V");

    fprintf(g,"\n");

}

void Rezolvare(){
int i, j, o;
lli dif;

    for(i=1;i<=N;i++)
        for(j=1;j<=N;j++)
            if( i != j ){

                CreareUNUDOI(i,j);

                if( UNU.size() >= 3 && DOI.size() >= 3 ){

                    Reordonare(UNU,rUNU);
                    Reordonare(DOI,rDOI);

                    if( ePolig(rUNU) && ePolig(rDOI) ){

                        dif = Modul( Aria(rUNU) - Aria(rDOI) );
                        Configuratie();

                        if( dif < DIF || ( dif == DIF && Comp() ) ){

                            DIF = dif;
                            for(o=1;o<=N;o++)
                                SOL[o] = sol[o];

                        }

                    }

                }

            }

    Afisare();

}

int main(){

    Citire();
    Rezolvare();

return 0;
}