Cod sursa(job #1660466)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 23 martie 2016 09:38:15
Problema Gradina Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.59 kb
#include<fstream>
#include<algorithm>
#include<cstring>
using namespace std;
int n, i, j, nr1, nr2, ii, ok;
struct point{
    int x;
    int y;
    int poz;
};
point p[255], p1[255], p2[255];
int sol[255], f[255], con[255], s[255];
long long minim, aria1, aria2;
ifstream fin("gradina.in");
ofstream fout("gradina.out");
long long det(int X1, int Y1, int X2, int Y2, int X3, int Y3){
    return (X2 - X1) * 1LL * (Y3 - Y1) - (X3 - X1) * 1LL * (Y2 - Y1);
}
long long modul(long long x){
    if(x > 0){
        return x;
    }
    return -x;
}
long long aria(point p[255], int n){
    long long a = 0;
    for(int i = 1; i < n - 1; i++){
        a += modul( det(p[i].x, p[i].y, p[i + 1].x, p[i + 1].y, p[i + 1].x, p[i + 1].y) );
    }
    if(a < 0){
        a = -a;
    }
    return a;
}
long long convex(point p[255], int n){
    memset(f, 0, sizeof(f));
    if(n < 3){
        return 1000000000000;
    }
    int u = 2;
    s[1] = 1;
    s[2] = 2;
    f[2] = 1;
    int i = 3, d = 1;
    for(i = 3; i >= 1; i+= d){
        if(f[i] == 1){
            continue;
        }
        while(u >= 2 && det(p[ s[u - 1] ].x, p[ s[u - 1] ].y, p[ s[u] ].x, p[ s[u] ].y, p[i].x, p[i].y) < 0){
            f[ s[u] ] = 0;
            u--;
        }
        f[i] = 1;
        u++;
        s[u] = i;
        if(i == n){
            d = -1;
        }
    }
    if(u - 1 != n){
        return 1000000000000LL;
    }
    else{
        long long a = 0;
        for(int i = 1; i < n - 1; i++){
            a += modul( det(p[ s[i] ].x, p[ s[i] ].y, p[ s[i + 1] ].x, p[ s[i + 1] ].y, p[ s[i + 2] ].x, p[s[i + 2] ].y) );
        }
        return a;
    }
}
int cmp(point a, point b){
    if(a.x != b.x){
        return a.x < b.x;
    }
    return a.y < b.y;
}
int main(){
    fin>> n;
    for(i = 1; i <= n; i++){
        fin>> p[i].x >> p[i].y;
        p[i].poz = i;
    }
    minim = 1000000000000LL;
    sort(p + 1, p + n + 1, cmp);
    for(i = 1; i <= n; i++){
        for(j = 1; j <= n; j++){
            if(i != j){
                nr1 = nr2 = 0;
                for(ii = 1; ii <= n; ii++){
                    if(ii == i){
                        nr1++;
                        p1[nr1] = p[ii];
                        con[ p[ii].poz ] = 1;
                    }
                    else{
                        if(ii == j){
                            nr2++;
                            p2[nr2] = p[ii];
                            con[p[ii].poz] = 2;
                        }
                        else{
                            if(det(p[ii].x, p[ii].y, p[i].x, p[i].y, p[j].x, p[j].y) > 0){
                                nr1++;
                                p1[nr1] = p[ii];
                                con[ p[ii].poz ] = 1;
                            }
                            else{
                                 nr2++;
                                 p2[nr2] = p[ii];
                                con[ p[ii].poz ] = 2;
                            }
                        }
                    }
                }
                aria1 = convex(p1, nr1);
                aria2 = convex(p2, nr2);
                if(aria1 != 1000000000000 && aria2 != 1000000000000){
                    if(modul(aria1 - aria2) < minim){
                        minim = modul(aria1 - aria2);
                        for(ii = 1; ii <= n; ii++){
                            sol[ii] = con[ii];
                        }
                    }
                    else{
                        if(modul(aria1 - aria2) == minim){
                            ok = 0;
                            for(ii = 1; ii <= n; ii++){
                                if(con[ii] < sol[ii]){
                                    ok = 1;
                                    break;
                                }
                                if(sol[ii] < con[ii]){
                                    break;
                                }
                            }
                            if(ok == 1){
                                for(ii = 1; ii <= n; ii++){
                                    sol[ii] = con[ii];
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    if(minim % 2 == 0){
        fout<< minim / 2 <<".0\n";
    }
    else{
        fout<< minim / 2 <<".5\n";
    }
    for(i = 1; i <= n; i++){
        if(sol[i] == 1){
            fout<<"I";
        }
        else{
            fout<<"V";
        }
    }
    return 0;
}