Cod sursa(job #2446954)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 11 august 2019 13:24:56
Problema Rubarba Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

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

const int NMAX = 1e5;

struct Punct
{
    long long x, y;
};

struct Dreapta
{
    double a, b, c;
};

int N;
Punct v[NMAX + 5];
vector <Punct> hull;

Dreapta dreapta(Punct p1, Punct p2)
{
    Dreapta d1 = {p2.y - p1.y, p1.x - p2.x, p1.y * p2.x - p1.x * p2.y};
    double aux = sqrt((double)d1.a * d1.a + d1.b * d1.b);
    double k = 1 / aux;
    d1.a *= k;
    d1.b *= k;
    d1.c *= k;
    return d1;
}

Dreapta perp(Punct a, Dreapta d)
{
    Dreapta d1 = {-d.b, d.a, d.b * a.x - d.a * a.y};
    double aux = sqrt((double)d1.a * d1.a + d1.b * d1.b);
    double k = 1 / aux;
    d1.a *= k;
    d1.b *= k;
    d1.c *= k;
    return d1;
}

double distd(Punct a, Dreapta d)
{
    return a.x * d.a + a.y * d.b + d.c;
}

long long cross_product(Punct P1, Punct P2, Punct P3)
{
    return (P2.x - P1.x) * (P3.y - P1.y) -
           (P2.y - P1.y) * (P3.x - P1.x);
}

inline bool cmp(const Punct A, const Punct B)
{
    return cross_product(v[1], A, B) < 0;
}

void ReadAndHull()
{
    fin >> N;

    int x, y;
    for(int i = 1; i <= N; i++)
    {
        fin >> x >> y;
        v[i] = {x, y};
    }

    for(int i = 2; i <= N; i++)
        if((v[i].x == v[1].x && v[i].y < v[1].y) || v[i].x < v[1].x)
            swap(v[1], v[i]);

    sort(v + 2, v + N + 1, cmp);

    hull.push_back(v[1]);
    for(int i = 2; i <= N; i++)
    {
        while (hull.size() > 1 && cross_product(hull[hull.size() - 2], hull[hull.size() - 1], v[i]) >= 0)
            hull.pop_back();

        hull.push_back(v[i]);
    }
}

const double INF = 2000000000;

void Solve()
{
    double ans = INF;

    for(int i = 0; i < hull.size(); i++)
    {
        long long ind1, ind2, ind3;
        double di1, di2, di3;
        di1 = di2 = -INF;
        di3 = INF;

        Dreapta d1;

        if(i == hull.size() - 1)
            d1 = dreapta(hull[hull.size() - 1], hull[0]);
        else
            d1 = dreapta(hull[i], hull[i + 1]);
        Dreapta d2 = perp(hull[i], d1);

        for (long long j = 0; j < hull.size(); ++j)
        {
            double dist1 = fabs(distd(hull[j], d1));
            double dist2 = distd(hull[j], d2);
            if (di1 < dist1)
            {
                di1 = dist1;
                ind1 = i;
            }
            if (di2 < dist2)
            {
                di2 = dist2;
                ind2 = i;
            }
            if (di3 > dist2)
            {
                di3 = dist2;
                ind3 = i;
            }
        }

        double dst = di2 - di3;
        ans = min(ans, dst * di1);
    }

    fout << ans << '\n';
}

int main()
{
    ReadAndHull();

    Solve();

    return 0;
}