Cod sursa(job #87960)

Utilizator andrei_infoMirestean Andrei andrei_info Data 29 septembrie 2007 21:35:19
Problema Rubarba Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.77 kb
#include <cstdio>
#include <algorithm>
#include <math.h>

using namespace std;

#define eps 0.000001
#define INF 0x7FFFFFFF
#define MAX 100005

struct point {
                double polar, x,y;
                };
point a[MAX],piv;
point st[MAX];
int n,nr; //n - nr de puncte; nr - numarul de puncte de pe infasuratoarea convexa

void citire()
{
        freopen("rubarba.in","r",stdin);
        scanf("%d", &n);
        for (int i = 0; i<n; i++)
                scanf("%lf %lf\n", &a[i].x, &a[i].y);
        fclose(stdin);
}

double upolar ( point pc, point piv ) //calc tangenta unghiul polar
{
        if ( fabs(pc.x - piv.x) < eps )
                return 999999999;
        return (pc.y - piv.y) / ( pc.x - piv.x);
}

void calc()
{
        int pmin =0;
        for (int i=1; i<n; i++) // afla pozitia punctului stanga jos
                if (a[i].x < a[pmin].x || (  fabs(a[i].x - a[pmin].x) < eps && a[i].y < a[pmin].y) )
                        pmin = i;
        swap (a[0], a[pmin]);
        piv = a[0];
        for (int i=1; i<n; i++)
                a[i].polar = upolar(a[i],piv);

        sort(a+1, a+n);
}

double dist ( point p1, point p2)
{
        return sqrt( pow(p1.x-p2.x,2) + pow(p1.y-p2.y,2) );
}

bool operator<(const point &pc1, const point &pc2) //modifica operatorul < pentru sortarea unghiurilor polare
{
if ( (pc1.polar < 0) ^ (pc2.polar < 0)  ) return pc1.polar < pc2.polar; // compara 2 unghiuri de semn opus
if (pc1.polar >= 0 && pc2.polar >=0) // unghiuri polare > 0
        if (fabs(pc1.polar-pc2.polar) > eps )
                return pc1.polar < pc2.polar;
        else
                return dist(pc1,piv) > dist(pc2,piv); // unghiuri polare egale, sortarea se face in functie de distanta de pivot
else
        if (fabs(pc1.polar-pc2.polar) > eps ) //unghiuri polare negative
                return pc1.polar < pc2.polar;
        else
                return dist(pc1,piv) < dist(pc2,piv); //unghiuri polare negative egale, sortare in functie de distanta de pivot
}

double cross(point p1, point p2, point p3) //calculeaza produsul incrucisat
{
        return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}

void graham()
{
        calc(); //calc unghiuri polare

        st[1] = a[0]; st[2] = a[1]; //introdu primele 2 puncte in stiva
        nr = 2;
        for (int i = 2; i<n; i++)
        {
                double c = -cross(st[nr], st[nr-1], a[i]);
                if ( fabs(c) < eps ) //elimina punctele coliniare de pe infasuratoarea convexa
                        st[nr] = a[i];
                else
                if ( fabs(c) > eps )
                        st[++nr] = a[i];
                else
                {
                        while ( c<0 && nr > 2)
                        {
                                nr--;
                                c=-cross(st[nr],st[nr-1],a[i]);
                        }
                st[++nr]=a[i];
                }
        }
        st[++nr] = a[0];
}

double linePointDist( point A, point B, point C) //dist AB la C
{
        double d = cross(A,B,C) / dist(A,B);
        return fabs(d);
}

void ec ( point A, point B, double &a, double &b, double &c)
{
    a = B.y - A.y;
    b = A.x - B.x;
    c = a * A.x + b*A.y;
};

point rotire( point A, double rad)
{
    point aux;
    if (rad >= 0 )
    {
        aux.x = A.x * cos(rad) + A.y * sin(rad);
        aux.y = -A.x * sin(rad) + A.y * cos(rad);
    }
    else
    {
        rad = fabs(rad);
        aux.x = A.x * cos(rad) - A.y *sin(rad);
        aux.y = A.x * sin(rad) + A.y * cos(rad);
    };
    return aux;
};

double arie_min ( point A, point B, int pozA, int pozB)
{
        double Lung = 0, Lat;

        for (int i =1; i <=nr; i++)
        {
            if (i == pozA || i == pozB) continue;

            double aux = linePointDist(A,B, st[i]);
            if (aux > Lung ) Lung =aux;
        };

        double a,b,c;
        ec(A,B, a,b,c);
        double rad,panta;
        panta = -double(a/b);
        if (a ==0|| b==0)
            rad=0;
        else
            rad = atan(panta);

        double xmin=INF, xmax=-INF;
        for ( int i = 1; i<=nr; i++)
        {
            point aux = rotire(st[i], rad);
            if (aux.x < xmin ) xmin = aux.x;
            if (aux.x > xmax ) xmax = aux.x;
        };
        Lat = xmax-xmin;
        return Lat * Lung;
};

void calc_amin()
{
    double arie=pow(10,13),aux;
    for (int i = 2; i<=nr ;i++)
    {
        aux=arie_min(st[i],st[i-1],i,i-1);
        if (aux < arie)
            arie = aux;
    };
    freopen("rubarba.out","w", stdout);
    printf("%.2lf", arie);
    fclose(stdout);
};

int main()
{
        citire();
        graham();
        calc_amin();

        return 0;

}