Cod sursa(job #3266780)

Utilizator tmxmatTudor Matasaru Mihai tmxmat Data 10 ianuarie 2025 14:22:04
Problema Rubarba Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 7.01 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
{
    double x;
    double y;
};

point p[100001];

vector<point> stiva;

int n;

int cross_prod(point a, point b, point c) /// produsul vectorial dintre vectorii ab si ac
{
    double 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
        /// ne trebuie asta pentru functia cmp()
    }
}

double absol(double a) /// functie valoare absoluta (in modul)
{
    return a < 0 ? -a : a;
}

double triangle_surface(point a, point b, point c) /// calcularea ariei triunghiului determinat de punctele a, b, c
{
    return 0.5 * absol(a.x * b.y + c.x * a.y + b.x * c.y - b.y * c.x - c.y * a.x - b.x * a.y);
}

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));
}

double dist_dreapta(point a, point b, point c) /// calcularea distantei de la punctul c la dreapta ab
{
    return 2 * triangle_surface(a, b, c) / dist_puncte(a, b);
}

bool cmp(point a, point b) /// functie de comparare pentru sort() pentru sortarea punctelor in ordine trigonometrica
{
    return cross_prod(p[1], a, b) > 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]); /// punctul cel mai de jos, (respectiv cel mai din stanga in caz de egalitate), este pus pe prima pozitie a sirului de puncte
    /// acesta va fi punctul origine
    sort(p + 2, p + n + 1, cmp); /// se sorteaza punctele in ordine trigonometrica fata de punctul origine
//    for (int i = 1; i <= n; i ++)
//    {
//        cout << p[i].x << " " << p[i].y << "\n";
//    }
    int top = 0;
    stiva.push_back(p[1]);
    stiva.push_back(p[2]);
    top ++;
    /// ne adaugam primele 2 puncte intr-o stiva si aplicam algoritmul graham's scan
    for (int i = 3; i <= n; i ++)
    {
        /// daca gasim un punct rotit mai mult in sens trigonometric decat ultimul punct din stiva fata de penultimul punct din stiva
        if (cross_prod(stiva[top - 1], stiva[top], p[i]) >= 0 || top < 1)
        {
            top ++;
            stiva.push_back(p[i]); /// atunci adaugam elementul
        }
        else /// daca nu, eliminam ultimele puncte din stiva cat timp nu respecta conditia
        {
            while (cross_prod(stiva[top - 1], stiva[top], p[i]) == -1)
            {
                top --;
                stiva.pop_back();
            }
            top ++;
            stiva.push_back(p[i]); /// adaugam la sfarsit elementul curent
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) /// citim elementele
    {
        cin >> p[i].x >> p[i].y;
    }
    if (n == 1) /// caz separat pentru n = 1 (fara el, se afiseaza -0.00)
    {
        cout << "0.00";
        return 0;
    }
    convex_hull();
    cout << fixed;
    /// solutie n^2 pentru problema rubarba
    double arie_min = 2e9;
    for (int i = 0; i < stiva.size(); i ++) /// pentru fiecare 2 puncte adiacente de pe infasuratoare (care determina un segment AB)
    {
//        cout << stiva[i].x << " " << stiva[i].y << "\n";
//        cout << stiva[(i + 1) % stiva.size()].x << " " << stiva[(i + 1) % stiva.size()].y << "\n\n";
        double d_paralel_capat1_max = -1;
        double d_paralel_capat2_max = -1;
        double d_perp_max = -1;
        for (int j = 0; j < stiva.size(); j ++) /// parcurgem restul punctelor (fie acestea C) si calculam:
        {
            double d1 = dist_puncte(stiva[i], stiva[j]); /// distanta de la C la A
            double d2 = dist_puncte(stiva[(i + 1) % stiva.size()], stiva[i]); /// distanta de la A la B (segmentul AB)
            double d3 = dist_puncte(stiva[(i + 1) % stiva.size()], stiva[j]); /// distanta de la C la B
            double distanta_perp = dist_dreapta(stiva[i], stiva[(i + 1) % stiva.size()], stiva[j]); /// distanta de la C la segmentul AB
            double d_capat1 = d1; /// distanta de la C la A (din nou)
            double d_capat2 = d3; /// distanta de la C la B (din nou)
            double d_paralel_capat1 = sqrt(d_capat1 * d_capat1 - distanta_perp * distanta_perp); /// lungimea proiectiei segmentului CA pe dreapta AB
            double d_paralel_capat2 = sqrt(d_capat2 * d_capat2 - distanta_perp * distanta_perp); /// lungimea proiectiei segmentului CB pe dreapta AB
            double angle1;
            double angle2;
            if (d1 == 0) /// cazuri pentru cand punctul C coincide cu A sau B, pentru a evita o impartire la 0
            {
                angle2 = 0;
            }
            else if (d3 == 0)
            {
                angle1 = 0;
            }
            else
            {
                angle1 = (d2 * d2 + d3 * d3 - d1 * d1) / (2 * d2 * d3); /// formula pentru calcularea cosinusului unghiului ABC
                angle2 = (d2 * d2 + d1 * d1 - d3 * d3) / (2 * d2 * d1); /// formula pentru calcularea cosinusului unghiului BAC
                /// facem asta pentru a vedea daca proiectia punctului C pe dreapta AB se afla si pe segmentul AB
            }
            if (angle1 <= 0 || angle2 <= 0) /// cosinusul unui unghi obtuz este mai mare sau egal cu 0 (egalitatea se atinge pentru un unghi de 90 de grade)
            {
                /// vrem sa calculam cele mai indepartate puncte din stanga segmentului AB, respectiv din dreapta segmentului AB
                /// pentru a determina lungimea dreptunghiului construit
                if (d_paralel_capat1 < d_paralel_capat2)
                {
                    d_paralel_capat1_max = max(d_paralel_capat1, d_paralel_capat1_max);
                }
                else
                {
                    d_paralel_capat2_max = max(d_paralel_capat2, d_paralel_capat2_max);
                }
            }
            d_perp_max = max(d_perp_max, distanta_perp); /// calculeaza cea mai mare distanta perpendiculara pe AB (latimea dreptunghiului)
        }
        double arie = (dist_puncte(stiva[i], stiva[(i + 1) % stiva.size()]) + d_paralel_capat1_max + d_paralel_capat2_max) * d_perp_max;
        arie_min = min(arie, arie_min); /// calculam aria
    }
    cout << setprecision(2) << arie_min; /// afisam aria cu 2 zecimale
    return 0;
}