Cod sursa(job #1135037)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 7 martie 2014 11:29:55
Problema Rubarba Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.36 kb
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>

using namespace std;

ifstream fin ("rubarba.in");
ofstream fout ("rubarba.out");

struct point
{
    int x,y;
}v[100001],s[100001];
int n,k;

double a,b,c,maxd,area=1e18;

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

bool cmp (point a, point b)
{
    return det (v[1],a,b) > 0;
}

double line_dist (point P)
{
    return fabs(a*P.x + b*P.y + c)/sqrt(a*a + b*b);
}

double line_dist_short (point P)
{
    return fabs(a*P.x + b*P.y + c);
}

int bs (int lo, int hi)
{
    if (hi < lo)
        return 0;

    int f = lo, l = hi, mid;
    double val;

    while (1)
    {
        mid = (lo + hi)/2;

        double Lval,Rval;

        val = line_dist_short (s[mid]);

        if (mid != f)
            Lval = line_dist_short (s[mid-1]);
        if (mid != l)
            Rval = line_dist_short (s[mid+1]);

        if ((mid == f || Lval <= val) && (mid == l || val >= Rval))
          break;

        if (mid > f && Lval > val)
            hi = mid-1;
        else lo = mid+1;
    }

    return mid;
}

int main()
{
    fin>>n;

    int mini = 1;

    for (int i=1; i<=n; ++i)
    {
        fin>>v[i].x>>v[i].y;

        if (v[i].x < v[mini].x || (v[i].x == v[mini].x && v[i].y < v[mini].y))
            mini = i;
    }

    swap (v[1],v[mini]);
    sort (v+2,v+n+1,cmp);

    k = 0;

    for (int i=1; i<=n; ++i)
    {
        while (k >= 2 && det (s[k-1],s[k],v[i]) <= 0)
            --k;
        s[++k] = v[i];
    }

    for (int i=1; i<k; ++i)
    {
        // dreapta care trece prin s[i] si s[i+1]
        a = s[i+1].y - s[i].y;
        b = s[i].x - s[i+1].x;
        c = 1LL*s[i].y*s[i+1].x - 1LL*s[i].x*s[i+1].y;

        int wh1 = bs (1,i);
        double d1 = line_dist (s[wh1]);

        int wh2 = bs (i+1,k);
        double d2 = line_dist (s[wh2]);

        //schimbam dreapta la una perpendiculara pe s[i] s[i+1]
        if (a != 0)
        {
            double m = b/a;
            a = m;
            b = -1;
            c = -m*s[i].x + s[i].y;
        }
        else
        {
            a = 1;
            b = 0;
            c = -s[i].x;
        }

        if (d1 > d2)
        {
            int l = bs (wh1,i);

            int r1 = bs (1,wh1);
            int r2 = bs (i+1,k);


            double dd = max (line_dist(s[r1]),line_dist(s[r2])) + line_dist(s[l]);

            area = min (area,d1*dd);
        }
        else
        {
            int r = bs (i+1,wh2);

            int l1 = bs (1,i);
            int l2 = bs (wh2,k);

            double dd = max (line_dist(s[l1]),line_dist(s[l2])) + line_dist(s[r]);

            area = min (area,d2*dd);
        }
    }

    //Perechea de puncte (1,k)

    a = s[k].y - s[1].y;
    b = s[1].x - s[k].x;
    c = 1LL*s[1].y*s[k].x - 1LL*s[1].x*s[k].y;

    int wh = bs (1,k);
    double d = line_dist (s[wh]);

    if (a != 0)
    {
        double m = b/a;
        a = m;
        b = -1;
        c = -m*s[1].x + s[1].y;
    }
    else
    {
        a = 1;
        b = 0;
        c = -s[1].x;
    }

    int l = bs (1,wh);
    int r = bs (wh,k);

    double dd = line_dist(s[l]) + line_dist(s[r]);

    area = min (area,d*dd);

    fout<<fixed<<setprecision (2)<<area;
}