Cod sursa(job #3342106)

Utilizator tmxmatTudor Matasaru Mihai tmxmat Data 22 februarie 2026 20:23:04
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.89 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>

using namespace std;

ifstream cin("rubarba.in");
ofstream cout("rubarba.out");

struct point
{
    long long x;
    long long y;
};

point p[100001];

vector<point> stiva;

int n;
double arie_min = 1e18;

long long cross_prod(point &a, point &b, point &c) /// produsul vectorial dintre vectorii ab si ac
{
    long long area = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);

    return area;

    if (area < 0)
    {
        return -1; /// C este rotit mai mult in sensul acelor de ceasornic decat B fata de punctul A
    }
    else if (area == 0)
    {
        return 0; /// punctele A, B, C sunt coliniare
    }
    else if (area > 0)
    {
        return 1; /// C este rotit mai mult in sens trigonometric decat B fata de punctul A
    }
}

long long dot_prod(point &a, point &b, point &c)
{
    long long rez = (b.x - a.x) * (c.x - a.x) + (b.y - a.y) * (c.y - a.y);

    return rez;
}

double dist_puncte(point &a, point &b) /// calcularea distantei dintre punctele a, b
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

bool cmp(point &a, point &b) /// functie de comparare pentru sort() pentru sortarea punctelor in ordine trigonometrica
{
    long long cp = cross_prod(p[1], a, b);
    if (cp == 0)
    {
        return dist_puncte(p[1], a) < dist_puncte(p[1], b);
    }
    return cp > 0;
}

void convex_hull() /// algoritmul "graham's scan" pentru determinarea infasuratorii convexe in O(n * log n)
{
    int minpos = 1;
    for (int i = 1; i <= n; i ++)
    {
        if (p[minpos].y > p[i].y)
        {
            minpos = i;
        }
        else if (p[minpos].y == p[i].y)
        {
            if (p[minpos].x > p[i].x)
            {
                minpos = i;
            }
        }
    }
    swap(p[minpos], p[1]);
    sort(p + 2, p + n + 1, cmp); /// se sorteaza punctele in ordine trigonometrica fata de punctul origine
    stiva.push_back(p[1]);
    stiva.push_back(p[2]);
    /// ne adaugam primele 2 puncte intr-o stiva si aplicam algoritmul graham's scan
    for (int i = 3; i <= n; i ++)
    {
        while (stiva.size() >= 2 && cross_prod(stiva[stiva.size() - 2], stiva[stiva.size() - 1], p[i]) <= 0)
        {
            stiva.pop_back();
        }
        stiva.push_back(p[i]);
    }
}

void rotating_calipers()
{
    int m = stiva.size();

    int top = 1;
    int right = 1;
    int left = 1;

    for (int i = 0; i < m; i ++)
    {
        point A = stiva[i];
        point B = stiva[(i + 1) % m];

        long long dx = B.x - A.x;
        long long dy = B.y - A.y;
        long long len_sq = dx * dx + dy * dy;

        while (abs(cross_prod(A, B, stiva[(top + 1) % m])) >= abs(cross_prod(A, B, stiva[top])))
        {
            top = (top + 1) % m;
        }

        while (dot_prod(A, B, stiva[(right + 1) % m]) >= dot_prod(A, B, stiva[right]))
        {
            right = (right + 1) % m;
        }
        if (i == 0)
        {
            left = right;
        }
        while (dot_prod(A, B, stiva[(left + 1) % m]) <= dot_prod(A, B, stiva[left]))
        {
            left = (left + 1) % m;
        }

        double height_times_len = abs(cross_prod(A, B, stiva[top]));
        double width_times_len = dot_prod(A, B, stiva[right]) - dot_prod(A, B, stiva[left]);

        double area = (height_times_len * width_times_len) / (double)len_sq;

        arie_min = min(area, arie_min);
    }
}

void read()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> p[i].x >> p[i].y;
    }
}

void process()
{
    convex_hull();
    rotating_calipers();
}

void print_result()
{
    cout << fixed << setprecision(2);
    cout << arie_min;
}

int main()
{
    read();
    process();
    print_result();
    return 0;
}