Cod sursa(job #1774827)

Utilizator Burbon13Burbon13 Burbon13 Data 9 octombrie 2016 14:58:22
Problema Gradina Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.72 kb
#include <cstdio>
#include <algorithm>
#define x first
#define y second

using namespace std;

const int nmx = 252;

struct punct
{
    punct()
    {

    }

    punct(int x_, int y_, int pos_)
    {
        x = x_;
        y = y_;
        pos = pos_;
    }

    double x,y;
    int pos;
};

const punct origine = punct(0,0,0);

int n;
punct p[nmx];

void citire()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%lf %lf", &p[i].x, &p[i].y);
        p[i].pos = i;
    }
}

int nr1, nr2;
punct v1[nmx], v2[nmx];
double minim = 99999999999999999;
bool acui[nmx];

double determinant(punct p1, punct p2, punct p3)
{
    return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}

void repartizare_puncte(punct p1, punct p2, double val)
{
    nr1 = 2;
    nr2 = 0;

    v1[1] = p1;
    v1[2] = p2;


    for(int i = 1; i <= n; ++i)
    {
        if(i == p1.pos || i == p2.pos)
            continue;

        if(determinant(p1,p2,p[i]) * val >= 0)
            v1[++nr1] = p[i];
        else
            v2[++nr2] = p[i];
    }
}

punct srt;

struct Cmp
{
    bool operator()(punct p1, punct p2)
    {
        return determinant(srt,p1,p2) > 0;
    }
} cmp;

void sortare(punct v[], int lungime)
{
    int pmin = 1;

    for(int i = 2; i <= lungime; ++i)
        if(v[i].x < v[pmin].x)
            pmin = i;
        else if(v[i].x == v[pmin].x && v[i].y < v[pmin].y)
            pmin = i;

    swap(v[1],v[pmin]);

    srt.x = v[1].x;
    srt.y = v[1].y;

    sort(v + 2, v + lungime + 1, cmp);
}

bool convex(punct v[], int lungime)
{
    for(int i = 2; i < lungime; ++i)
        if(determinant(v[i-1],v[i],v[i+1]) < 0)
            return false;

    if(determinant(v[lungime],v[1],v[2]) < 0)
        return false;

    if(determinant(v[lungime-1],v[lungime],v[1]) < 0)
        return false;

    return true;
}

double modul(double val)
{
    return val > 0 ? val : - val;
}

double arie(punct v[], int lungime)
{
    double ar = 0;

    for(int i = 2; i <= lungime; ++i)
        ar += determinant(origine,v[i-1],v[i]);

    ar += determinant(origine,v[lungime],v[1]);

    return modul(ar) / 2;
}

void atribuire_stalpi()
{
    for(int i = 1; i <= nr1; ++i)
        acui[v1[i].pos] = 0;

    for(int i = 1; i <= nr2; ++i)
        acui[v2[i].pos] = 1;
}

void calcul()
{
    if(convex(v1,nr1) && convex(v2,nr2))
    {
        double diferenta = modul(arie(v1,nr1) - arie(v2,nr2));
        if(diferenta < minim)
        {
            minim = diferenta;
            atribuire_stalpi();
        }
    }
}

void impartire()
{
    for(int i = 1; i < n; ++i)
        for(int j = i + 1; j <= n; ++j)
        {

            repartizare_puncte(p[i],p[j],1);

            if(nr1 >= 3 && nr2 >= 3)
            {
                sortare(v1,nr1);
                sortare(v2,nr2);
                calcul();
            }

            repartizare_puncte(p[i],p[j],-1);

            if(nr1 >= 3 && nr2 >= 3)
            {
                sortare(v1,nr1);
                sortare(v2,nr2);
                calcul();
            }
        }
}

void afish()
{
    printf("%.1f\n", minim);

    if(acui[1] == 1)

    {
        for(int i = 1; i <= n; ++i)
            if(acui[i] == 1)
                printf("I");
            else
                printf("V");
    }
    else
    {
        for(int i = 1; i <= n; ++i)
            if(acui[i] == 1)
                printf("V");
            else
                printf("I");
    }
}

int main()
{
    freopen("gradina.in", "r", stdin);
    freopen("gradina.out", "w", stdout);
    citire();
    impartire();
    afish();
    return 0;
}