Cod sursa(job #1460591)

Utilizator ZenusTudor Costin Razvan Zenus Data 13 iulie 2015 12:16:36
Problema Rubarba Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.61 kb
// Ideea de baza este ca una din laturile dreptunghiului coincide cu o latura de pe infasuratoare
// Iar celelalte delimitari sunt : cel mai departat punct , cel mai departat din stanga punct , si
// ce mai departat din dreapta punct. Acestea fiind in ordine trigonometrica sau anti, putem folosi
// cautarea binara pentru a le determina , asadar un O(H) pentru fiecare dreapta fixata si
// O(log(H)) pentru gasirea celorlalte trei puncte

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define point pair < double , double >

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

const int NSIZE = 100000 + 10;

point p[NSIZE] , hull[NSIZE];
int sizeHull , N;
double aCoef , bCoef , cCoef;

double cross(point A,point B,point C)
{
    double a = A.y - B.y;
    double b = B.x - A.x;
    double c = A.x * B.y - B.x * A.y;

    double product = a * C.x + b * C.y + c;

    return product;
}

bool compare(point A,point B)
{
    return (cross(p[1] , A , B) > 0);
}

void read()
{
    fin >> N;

    for (int i = 1 ; i <= N ; ++i)
    fin >> p[i].x >> p[i].y;
}

double getDistance(point p)
{
    double f = (aCoef * p.x + bCoef * p.y + cCoef) / sqrt(aCoef * aCoef + bCoef * bCoef);
    return (f > 0) ? f : -f;
}

double lineDist(point p)
{
    double f = aCoef * p.x + bCoef * p.y + cCoef;
    return (f > 0) ? f : -f;
}

int binarySearch(int le , int ri)
{
    int f = 0 , _le = le , _ri = ri;

    if (le > ri) return 0;

    while (true)
    {
        int mid = (le + ri) >> 1;

        double crtValue = lineDist(hull[mid]);
        double leftValue , rightValue;

        if (mid != _le) leftValue = lineDist(hull[mid - 1]);
        if (mid != _ri) rightValue = lineDist(hull[mid + 1]);

        if ((mid == _le || leftValue <= crtValue) && (mid == _ri || rightValue <= crtValue))
        return mid;

        (mid > _le && leftValue > crtValue) ? ri = mid - 1 : le = mid + 1;
    }
}

void convexHull()
{
    int _i = 1;
    stack < point > inStack;

    for (int i = 1 ; i <= N ; ++i)
    if (p[i] < p[1]) swap(p[1] , p[i]);

    sort(p + 2 , p + N + 1 , compare);

    inStack.push(p[1]);
    inStack.push(p[2]);

    for (int i = 3 ; i <= N ; ++i)
    {
        while (inStack.size() >= 2)
        {
            point prv = inStack.top();
            inStack.pop();

            point prvv = inStack.top();

            if (cross(prvv , prv , p[i]) <= 0) continue;
            else
            {
                inStack.push(prv);
                break;
            }
        }

        inStack.push(p[i]);
    }

    while (inStack.size())
    {
        hull[++sizeHull] = inStack.top();
        inStack.pop();
    }

    reverse(hull + 1 , hull + sizeHull + 1);
}

void solve()
{
    hull[sizeHull + 1] = hull[1];
    double answer = 1ll << 60;

    for (int i = 1 ; i <= sizeHull ; ++i)
    {
        aCoef = hull[i + 1].y - hull[i].y;
        bCoef = hull[i].x - hull[i + 1].x;
        cCoef = hull[i].y * hull[i + 1].x - hull[i].x * hull[i + 1].y;

        int _left = binarySearch(1 , i);
        int _right = binarySearch(i + 1 , sizeHull);
        double leftDistance = getDistance(hull[_left]);
        double rightDistance = getDistance(hull[_right]);

        int furthest = (leftDistance > rightDistance) ? _left : _right;

        if (aCoef != 0)
        {
            double m = bCoef / aCoef;
            aCoef = m;
            bCoef = -1;
            cCoef = (-1) * m * hull[furthest].x + hull[furthest].y;
        }

        if (leftDistance > rightDistance)
        {
            //iau intervalul unde se afla distanta mai mare [1 , i]
            //il impart in doua bucati dupa furthest si iau cele mai indepartate din cele doua intervale

            int _x = binarySearch(1 , furthest);
            int _y = binarySearch(furthest , i);

            int _z = binarySearch(i + 1 , sizeHull);

            answer = min(answer , leftDistance *
                    (max(getDistance(hull[_x]) , getDistance(hull[_z])) + getDistance(hull[_y])));
        }
        else
        {
            //analog daca e in [i + 1 , sizeHull]

            int _x = binarySearch(i + 1 , furthest);
            int _y = binarySearch(furthest , sizeHull);

            int _z = binarySearch(1 , i);

            answer = min(answer , rightDistance *
                    (max(getDistance(hull[_y]) , getDistance(hull[_z])) + getDistance(hull[_x])));
        }
    }

    fout << fixed << setprecision(2) << answer << '\n';
}

int main()
{

read();
convexHull();
solve();

return 0;
}