Cod sursa(job #875145)

Utilizator andreea29Iorga Andreea andreea29 Data 9 februarie 2013 19:08:25
Problema Rubarba Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.15 kb
#include<fstream>
#include<algorithm>
#include<cmath>
#include<iostream>

#define Nmax 100010
#define INFI 0x3f3f3f3f

using namespace std;

int n, st[Nmax], viz[Nmax], k;

struct punct {
    int x;
    int y;
} p[Nmax];

int cmp (punct a, punct b)
{
    if (a.x > b.x)
        return 0;
    if (a.x == b.x && a.y > b.y)
        return 0;
    return 1;
}

double det (punct a, punct b, punct c)
{
    return (b.x * c.y + c.x * a.y + a.x * b.y) - (a.y * b.x + b.y * c.x + c.y * a.x);
}

int semn (punct a, punct b, punct c)
{
    double d = det (a, b, c);
    if(fabs(d) < 0.0000000001)
        return 0;
    if (d > 0)
        return 1;
    else
        return 2;
}

void convex ()
{
    st[0] = 0;
    st[1] = 1;
    viz[1] = 1;
    int s = 1; //semn (p[0], p[1], p[2]);
    k = 1;
    int i = 2;
    while (i < n)
    {
        int s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
        while (s != s1 && s1 != 0)
        {
            viz[st[k]] = 0;
            --k;
            s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
        }
        ++k;
        st[k] = i;
        viz[i] = 1;
        ++i;
    }
    --i;
    while (i >= 0)
    {
        while (viz[i] && i >= 0)
            --i;
        if (i < 0)
            break;
        int s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
        while (s != s1 && s1 != 0)
        {
            --k;
            s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
        }
        ++k;
        st[k] = i;
        --i;
    }

}

double dist (int i, int j)
{
    return sqrt(double(((p[i].x - p[j].x) * (p[i].x - p[j].x)) + ((p[i].y - p[j].y) * (p[i].y - p[j].y))));
}


double proiectie (int i, int j, int k)
{
    double ar = det (p[i], p[j], p[k]);
    ar = abs(ar);
    return ar / dist (i, j);
}

double amax (int i1, int i2)
{
    double maxh = -1;
    double d1, d2;
    double max1 = 0;
    double max2 = 0;
    double da = dist (i1, i2);
    for (int i = 0; i < k; ++i)
    {
        if (st[i] != i1 && st[i] != i2)
        {
            double pr = proiectie (i1, i2, st[i]);
            if (pr > maxh)
                maxh = pr;
            d1 = dist (i1, st[i]);
            d2 = dist (i2, st[i]);
            d1 = sqrt (double (d1 * d1 - pr * pr));
            d2 = sqrt (double (d2 * d2 - pr * pr));
            if (d1 > da && d2 > max2)
                max2 = d2;
            else
                if (d2 > da && d1 > max1)
                    max1 = d1;
        }
    }
    return maxh * (max2 + max1 + da);
}

int main()
{
    ifstream f("rubarba.in");
    ofstream h("rubarba.out");
    f >> n;
    for (int i = 0; i < n; ++i)
    {
        f >> p[i].x >> p[i].y;
    }
    f.close();

    sort(p, p + n, cmp);

    convex ();

    double minim = INFI;

    for (int i = 0; i < k; ++i)
    {
        double blabla = amax (st[i], st[i + 1]);
        if (blabla < minim)
            minim = blabla;
       // cout << blabla << '\n';
    }

    //for (int i = 0; i < k; ++i)
        //h << st[i] << " ";

    minim = (int (minim * 100));
    minim = minim / 100;

    h << minim << '\n';

    h.close();
    return 0;
}