Cod sursa(job #3266416)

Utilizator tmxmatTudor Matasaru Mihai tmxmat Data 8 ianuarie 2025 16:54:40
Problema Rubarba Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.76 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)
{
    double area = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    if (area < 0)
    {
        return -1; /// CA is turned clockwise over BA
    }
    else if (area == 0)
    {
        return 0; /// CA is colinear with BA
    }
    else if (area > 0)
    {
        return 1; /// CA is turned counter clockwise over BA
        /// this is what we need here
    }
}

double absol(double a)
{
    return a < 0 ? -a : a;
}

double triangle_surface(point a, point b, point 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)
{
    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)
{
    return 2 * triangle_surface(a, b, c) / dist_puncte(a, b);
}

bool cmp(point a, point b)
{
    return cross_prod(p[1], a, b) > 0;
}

void convex_hull()
{
    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);
//    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 ++;
    for (int i = 3; i <= n; i ++)
    {
        if (cross_prod(stiva[top - 1], stiva[top], p[i]) >= 0 || top < 1)
        {
            top ++;
            stiva.push_back(p[i]);
        }
        else
        {
            while (cross_prod(stiva[top - 1], stiva[top], p[i]) == -1)
            {
                top --;
                stiva.pop_back();
            }
            top ++;
            stiva.push_back(p[i]);
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> p[i].x >> p[i].y;
        p[i].x *= 10;
        p[i].y *= 10;
    }
    convex_hull();
    cout << fixed;
    /// solutie n^2
    double arie_min = 2e9;
    for (int i = 0; i < stiva.size(); i ++)
    {
//        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 ++)
        {
            double distanta_perp = dist_dreapta(stiva[i], stiva[(i + 1) % stiva.size()], stiva[j]);
            double d_capat1 = dist_puncte(stiva[i], stiva[j]);
            double d_capat2 = dist_puncte(stiva[(i + 1) % stiva.size()], stiva[j]);
            double d_paralel_capat1 = sqrt(d_capat1 * d_capat1 - distanta_perp * distanta_perp);
            double d_paralel_capat2 = sqrt(d_capat2 * d_capat2 - distanta_perp * distanta_perp);
            double d1 = dist_puncte(stiva[i], stiva[j]);
            double d2 = dist_puncte(stiva[(i + 1) % stiva.size()], stiva[i]);
            double d3 = dist_puncte(stiva[(i + 1) % stiva.size()], stiva[j]);
            double angle1;
            double angle2;
            if (d1 == 0)
            {
                angle2 = 0;
            }
            else if (d3 == 0)
            {
                angle1 = 0;
            }
            else
            {
                angle1 = (d2 * d2 + d3 * d3 - d1 * d1) / (2 * d2 * d3);
                angle2 = (d2 * d2 + d1 * d1 - d3 * d3) / (2 * d2 * d1);
            }
            if (angle1 < 0 || angle2 < 0)
            {
                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);
        }
        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);
    }
    int rezultat = (double)arie_min;
    int zecimale = rezultat % 100;
    cout << setprecision(2) << rezultat / 100 << "." << zecimale;
    return 0;
}