Cod sursa(job #1673676)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 4 aprilie 2016 00:00:22
Problema Gradina Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.87 kb
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<deque>
#include<bitset>
#define x first.first
#define y first.second
#define p second
using namespace std;
pair< pair< int, int >, int  > v[260],a,b,c;
vector<int>X,Y;
deque<int>Z,W;
bitset<260>R,T;
int n,m,aa,bb,op,q,vmin,i,j,k,l,r,al,ar;
FILE *f,*g;
int modul(int a){
    if( a < 0 )
        return -a;
    return a;
}
long long det(int x1, int y1, int x2, int y2, int x3, int y3) {
    return (x2-x1) * (y3-y1) - (x3-x1) * (y2-y1);
}
int poly(vector <int> X, deque<int> &Z) {
    Z.clear();
    Z.push_back( X[0] );
    for(int i=1 ; i < X.size() - 1 ; i++ ) {
        if ( det( v[ X[0] ].x, v[ X[0] ].y, v[ X[ X.size() - 1 ] ].x, v[ X[ X.size() - 1 ] ].y , v[ X[i] ].x, v[ X[i] ].y) > 0){
            Z.push_back( X[i] );
        } else {
            Z.push_front( X[i] );
        }
    }
    Z.push_back( X[ X.size()-1 ] );
    Z.push_back( Z.front() );
    for (int i=0 ; i < Z.size() - 2 ; i++ ) {
        if (det( v[ Z[i] ].x, v[ Z[i] ].y, v[ Z[i+1] ].x, v[ Z[i+1] ].y, v[ Z[i+2] ].x, v[ Z[i+2] ].y ) > 0) {
            return 0;
        }
    }
    return 1;
}
int arie(deque <int> Z) {
    int r = 0;
    while(1){
        aa = Z.front();
        Z.pop_front();
        if (Z.empty())
            break;
        bb = Z.front();
        r += det( 0 , 0 , v[ aa ].x , v[ aa ].y , v[ bb ].x , v[ bb ].y );
    }
    return modul(r);
}
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);
    vmin = 2000000000;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if( i != j ){
                X.clear();
                Y.clear();
                for(k=1;k<=n;k++){
                    if( i == k )
                        X.push_back(i);
                    else if( j == k )
                        Y.push_back(j);
                    else if( det( v[i].x, v[i].y , v[j].x, v[j].y , v[k].x, v[k].y ) < 0 )
                        X.push_back(k);
                    else
                        Y.push_back(k);
                }
                if( X.size() >= 3 && Y.size() >= 3  ){
                    l = poly( X , Z );
                    r = poly( Y , W );
                    if( l && r ){
                        al = arie( Z );
                        ar = arie( W );
                        if( vmin > modul( al - ar ) ){
                            vmin = modul( al - ar );
                            R.reset();
                            for(k=0;k<X.size();k++) {
                                R[ v[ X[k] ].p ] = 1;
                            }
                            if( R[1] == 0 )
                                R = ~R;
                        }
                        else if( vmin == modul( al - ar ) ){
                            T.reset();
                            for (k=0;k<X.size();k++) {
                                T[ v[ X[k] ].p ] = 1;
                            }
                            if( T[1] == 0 )
                                T = ~T;
                            for(k=1;k<=n;k++){
                                if( R[i] != T[i] ) {
                                    if( R[i] == 0 )
                                        R = T;
                                     break;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    fprintf(g,"%d",vmin/2);
    if( vmin % 2 )
        fprintf(g,".5\n");
    else
        fprintf(g,".0\n");
    for(i=1;i<=n;i++){
        if( R[i] == 1 )
            fprintf(g,"I");
        else
            fprintf(g,"V");
    }
    fclose(f);
    fclose(g);
    return 0;
}