Cod sursa(job #1787792)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 25 octombrie 2016 00:09:58
Problema Gradina Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.43 kb
#include <cstdio>
#include <algorithm>

#define MAXN 250

long long rez=-1;
int n, sol[2][MAXN+1];
char ans[MAXN], aux[MAXN];
struct myc{
    int x, y, z;
    bool operator<(const myc u)const{
        if(x!=u.x) return x<u.x;
        else return y<u.y;
    }
}v[MAXN];

inline long long myabs(long long x){
    if(x<0) return -x;
    else return x;
}

inline long long arie(int i, int j, int p){
    return 1LL*v[i].x*v[j].y-1LL*v[j].x*v[i].y+1LL*v[j].x*v[p].y-1LL*v[p].x*v[j].y+1LL*v[p].x*v[i].y-1LL*v[i].x*v[p].y;
}

inline long long convex(int r[]){
    int a=0, b=1;
    long long ans=0;
    for(int i=2; i<r[0]; i++){
        if(arie(r[1], r[r[0]], r[i])>0){
            if(a==0) a=1, b=i;
            else{
                if(arie(r[a], r[b], r[i])>0) return 0;
                a=b;
                b=i;
                ans+=arie(r[1], r[b], r[a]);
            }
        }
    }
    if((a)&&(arie(r[a], r[b], r[r[0]])>0)) return 0;
    a=b;
    b=r[0];
    if(a!=1) ans+=arie(r[1], r[b], r[a]);
    for(int i=r[0]-1; i>1; i--){
        if(arie(r[1], r[r[0]], r[i])<0){
            if(arie(r[a], r[b], r[i])>0) return 0;
            a=b;
            b=i;
            ans+=arie(r[1], r[b], r[a]);
        }
    }
    if(arie(r[a], r[b], r[1])>0) return 0;
    return ans;
}

inline void solutie(){
    if(sol[0][0]<3) return ;
    if(sol[1][0]<3) return ;
    long long arie1=convex(sol[0]);
    if(arie1==0) return;
    long long arie2=convex(sol[1]);
    if(arie2==0) return ;
    if((rez==-1)||(myabs(arie1-arie2)<rez)){
        rez=myabs(arie1-arie2);
        for(int i=1; i<=sol[0][0]; i++) ans[v[sol[0][i]].z]='I';
        for(int i=1; i<=sol[1][0]; i++) ans[v[sol[1][i]].z]='V';
        if(ans[0]=='V')
            for(int i=0; i<n; i++)
                if(ans[i]=='I') ans[i]='V';
                else ans[i]='I';
    }else if(myabs(arie1-arie2)==rez){
        for(int i=1; i<=sol[0][0]; i++) aux[v[sol[0][i]].z]='I';
        for(int i=1; i<=sol[1][0]; i++) aux[v[sol[1][i]].z]='V';
        if(aux[0]=='V')
            for(int i=0; i<n; i++)
                if(aux[i]=='I') aux[i]='V';
                else aux[i]='I';
        int p=0;
        while((p+1<n)&&(aux[p]==ans[p])) p++;
        if(aux[p]<ans[p]){
            while(p<n){
                ans[p]=aux[p];
                p++;
            }
        }
    }
}

int main(){
    int l;
    FILE *fin, *fout;
    fin=fopen("gradina.in", "r");
    fout=fopen("gradina.out", "w");
    fscanf(fin, "%d", &n);
    for(int i=0; i<n; i++){
        fscanf(fin, "%d%d", &v[i].x, &v[i].y);
        v[i].z=i;
    }
    std::sort(v, v+n);
    for(int i=0; i<n; i++){
        for(int j=0; j<i; j++){
            sol[0][0]=sol[1][0]=0;
            for(int p=0; p<n; p++){
                if((p!=i)&&(p!=j)){
                    l=arie(i, j, p)>0;
                    sol[l][++sol[l][0]]=p;
                }else sol[0][++sol[0][0]]=p;
            }
            solutie();
            sol[0][0]=sol[1][0]=0;
            for(int p=0; p<n; p++){
                if((p!=i)&&(p!=j)){
                    l=arie(i, j, p)>0;
                    sol[l][++sol[l][0]]=p;
                }else sol[1][++sol[1][0]]=p;
            }
            solutie();
        }
    }
    fprintf(fout, "%.1lf\n", rez*0.5);
    for(int i=0; i<n; i++)
        fputc(ans[i], fout);
    fputc('\n', fout);
    fclose(fin);
    fclose(fout);
    return 0;
}