Cod sursa(job #88053)

Utilizator andrei_infoMirestean Andrei andrei_info Data 29 septembrie 2007 23:43:42
Problema Rubarba Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.09 kb
#include <cstdio>
#include <algorithm>
#include <math.h>

using namespace std;

#define eps 0.0001
#define INF 200000000
#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);
}

inline double upolar ( point pc, point piv ) //calc tangenta unghiul polar
{
        if ( fabs(pc.x - piv.x) < eps )
                return 1/0;
        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);
}

inline 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
}

inline 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 ( 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];
}

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

inline 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;
    double s = sin(rad);
    //double c = cos(rad);
    double c = sqrt( 1-pow(s,2));

    if (rad < 0) rad =-rad;
    if (rad >= 0 )
    {

        aux.x = A.x * c + A.y * s;
        aux.y = -A.x * c + A.y * s;
    }
    else
    {

        aux.x = A.x * c - A.y *s;
        aux.y = A.x * s + A.y * c;
    };
    return aux;
};

inline point intersect( double &a, double &b, double &c, double &a2, double &b2, double &c2)
{
    double det = a*b2 - a2*b;
    point aux;
    if(det == 0){
        aux.polar= 0;
    }else{
        aux.x = (b2*c - b*c2)/det;
        aux.y = (a*c2 - a2*c)/det;
        aux.polar = 1;
    }
    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 panta;
        double xmin=INF, xmax=-INF;
        double ymin=INF, ymax=-INF;
        if ( b == 0 || a==0)
        {
            if (a ==0)
                for (int i = 1; i<nr; i++)
                {
                    if (st[i].x < xmin ) xmin = st[i].x;
                    if (st[i].x > xmax ) xmax = st[i].x;
                    ymin = 0; ymax = 0;

                }
            else
                for (int i = 1; i<nr; i++)
                {
                    if (st[i].y < xmin ) xmin = st[i].y;
                    if (st[i].y > xmax ) xmax = st[i].y;
                    ymin = 0 ; ymax = 0;


                };
        }
        else
        {
            panta = 1/double(a/b);

            for ( int i = 1; i<nr; i++)
            {
                double a2,b2,c2;
                a2 = -panta;
                b2 = 1;
                c2 = st[i].y - panta*st[i].x;
                point aux = intersect(a,b,c, a2,b2,c2);
                if (aux.polar > eps)
                {
                    if (aux.x < xmin )   xmin = aux.x;
                    if (aux.x > xmax )   xmax = aux.x;
                    if (aux.y < ymin )   ymin = aux.y;
                    if (aux.y > ymax )   ymax = aux.y;
                };
            };
        };
        Lat = sqrt( pow(xmax-xmin,2) + pow(ymax-ymin,2));
        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\n", arie);
    fclose(stdout);
};

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

        return 0;

}