Cod sursa(job #3342101)

Utilizator tmxmatTudor Matasaru Mihai tmxmat Data 22 februarie 2026 19:40:51
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.11 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;
long 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);
    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
    }
}

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()
{
    for (int i = 0; i < stiva.size(); i ++)
    {
        point *A = &stiva[i];
        point *B = &stiva[(i + 1) % stiva.size()];

        /// componentele vectorului AB
        long double dx = B->x - A->x;
        long double dy = B->y - A->y;
        long double len = dist_puncte(*A, *B);
        long double ux = dx; /// / len
        long double uy = dy; /// / len

        long double rot90_ux = -uy;
        long double rot90_uy = ux;

        long double min_proj_C_AB = 1e18;
        long double max_proj_C_AB = -1e18;
        long double min_proj_C_rot90_AB = 1e18;
        long double max_proj_C_rot90_AB = -1e18;

        for (int j = 0; j < stiva.size(); j ++)
        {
            point *C = &stiva[j];

            long double proj_C_AB = (C->x - A->x) * ux + (C->y - A->y) * uy; /// AC * cos alpha
            long double proj_C_rot90_AB = (C->x - A->x) * rot90_ux + (C->y - A->y)  * rot90_uy; /// AC * cos (90 - alpha) (aka AC * sin alpha)

            min_proj_C_AB = min(min_proj_C_AB, proj_C_AB);
            max_proj_C_AB = max(max_proj_C_AB, proj_C_AB);
            min_proj_C_rot90_AB = min(min_proj_C_rot90_AB, proj_C_rot90_AB);
            max_proj_C_rot90_AB = max(max_proj_C_rot90_AB, proj_C_rot90_AB);
        }

        long double lungime = max_proj_C_AB - min_proj_C_AB;
        long double latime = max_proj_C_rot90_AB - min_proj_C_rot90_AB;

        long double arie = lungime * latime / len / len;
        arie_min = min(arie_min, arie);
    }
}

void read()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) /// citim elementele
    {
        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;
}