Cod sursa(job #3221217)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 6 aprilie 2024 12:19:59
Problema Rubarba Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.69 kb
#include <bits/stdc++.h>
using namespace std;
const string TASK("rubarba");
ifstream fin(TASK + ".in");
ofstream fout(TASK + ".out");
#define cin fin
#define cout fout

#define dd long long
#define point complex<dd>
#define x real()
#define y imag()

const int N = 120009;
const double eps = 1e-9;

long long dot_product(point a, point b){return (conj(a) * b).x;}
long long cross_product(point a, point b){return (conj(a) * b).y;}
long long distance(point a, point b){return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));}
long long distance(point a, point b, point x){return abs(cross_product(a - x, b - x)) / distance(a, b);}
long long area(point a, point b, point c){return abs(cross_product(a - c, b - c));}

int n, sz;
point p[N], stk[N];

int next(int k)
{
    return (k == n - 1) ? 0 : (k + 1);
}


void find_extremes(int b1, int& b2, int& r, int& a, int& l)
{
    b2 = next(b1);
    point base = p[b2] - p[b1];

    while(dot_product(base, p[next(r)] - p[b1]) > dot_product(base, p[r] - p[b1]))
        r = next(r);

    a = r;
    while(area(p[b1], p[b2], p[next(a)]) > area(p[b1], p[b2], p[a]))
        a = next(a);

    l = a;
    while(dot_product(base, p[next(l)] - p[b1]) < dot_product(base, p[l] - p[b1]))
        l = next(l);
}

long double rectangle_area(int b1, int b2, int r, int a, int l)
{
    return (long double)dot_product(p[b2] - p[b1], p[r] - p[l])
    / dot_product(p[b2] - p[b1], p[b2] - p[b1])
    * area(p[b1], p[b2], p[a]);
}


long double Rotating_Calipers()
{
    int j, r = 1, a, l;
    long double min_area = 0, area;

    for(int i = 0; i < n; ++i)
    {
        find_extremes(i, j, r, a, l);
        area = rectangle_area(i, j, r, a, l);
        if(!i || area < min_area)
            min_area = area;
    }

    return min_area;
}

signed main()
{
    cin >> n;

    double a, b;
    for(int i = 1; i <= n; ++i)
    {
        cin >> a >> b;
        p[i] = a + 1i * b;
    }

    if(n <= 2)
    {
        cout << "0\n";
        return 0;
    }

    int j = 1;
    for(int i = 2; i <= n; ++i)
        if(p[i].x < p[j].x || (p[i].x == p[j].x && p[i].y < p[j].y))
            j = i;

    swap(p[1], p[j]);

    sort(p + 2, p + n + 1, [](point a, point b){return cross_product(a - p[1], b - p[1]) < 0;});

    stk[++ sz] = p[1];
    for(int i = 2; i <= n; ++i)
    {
        while(sz > 1 && cross_product(stk[sz] - stk[sz - 1], p[i] - stk[sz - 1]) > 0)-- sz;
        stk[++ sz] = p[i];
    }

    for(int i = 1; i <= sz; ++i)p[i - 1] = stk[i];
    n = sz;


    ///in p am infasuratoarea convexa, in ordine

    cout << fixed << setprecision(2) <<
    Rotating_Calipers();

    return 0;
}