Cod sursa(job #3031751)

Utilizator Andrei_ierdnANeculau Rares-Andrei Andrei_ierdnA Data 20 martie 2023 19:03:06
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.47 kb
#include <fstream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

ifstream f("rubarba.in");
ofstream g("rubarba.out");

#define CCW 1
#define CW -1
#define COL 0

#define LESS90 1
#define MORE90 -1
#define JUST90 0


struct Fraction
{
    long long sus, jos;
};

bool operator < (const Fraction &a, const Fraction &b)
{
    return (a.sus * b.jos < a.jos * b.sus);
}

bool operator == (const Fraction &a, const Fraction &b)
{
    return (a.sus * b.jos == a.jos * b.sus);
}

bool operator > (const Fraction &a, const Fraction &b)
{
    return (a.sus * b.jos > a.jos * b.sus);
}



struct Punct
{
    long long x, y;
    void rotateCCW()
    {
        this->y = -this->y;
        swap(this->x, this->y);
    }
    void translate(long long dx, long long dy)
    {
        this->x += dx;
        this->y += dy;
    }
    void operator = (const Punct &other)
    {
        this->x = other.x;
        this->y = other.y;
    }
};

bool operator < (const Punct &a, const Punct &b)
{
    if (a.x < b.x)
        return true;
    if (a.x == b.x) {
        if (a.y < b.y)
            return true;
    }
    return false;
}

bool operator == (const Punct &a, const Punct &b)
{
    return (a.x == b.x && a.y == b.y);
}



struct Segment
{
    Punct a, b;
    void translate(long long x, long long y)
    {
        this->a.translate(x, y);
        this->b.translate(x, y);
    }
};



int getOrientation(const Punct &a, const Punct &b, const Punct &c)
{
    long long crossProduct = (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
    if (crossProduct > 0)
        return CCW;
    if (crossProduct < 0)
        return CW;
    return COL;
}

int getRightAngleOffset(const Punct &a1, const Punct &a2, const Punct &b1, const Punct &b2)
{
    long long dotProduct = (a2.x - a1.x) * (b2.x - b1.x) + (a2.y - a1.y) * (b2.y - b1.y);
    if (dotProduct > 0)
        return LESS90;
    if (dotProduct < 0)
        return MORE90;
    return JUST90;
}

long long getTriangleArea(const Punct &a, const Punct &b, const Punct &c)
{
    /// WARNING! IT'S DOUBLED!
    if (a == b || b == c || c == a)
        return 0;
    return abs((b.x - a.x) * (b.y + a.y) + (c.x - b.x) * (c.y + b.y) + (a.x - c.x) * (a.y + c.y));
}

long long getDist(const Punct &a, const Punct &b)
{
    /// WARNING! IT'S SQUARED!
    return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
}



long long n, i, j, k, l, area, area2;
Punct v[100100], aux, aux2;
vector<int> lowerHull, upperHull;
long long rect1, rect2, rectdiv;
long double decarea, finalarea;
bool setarea;

int main()
{
    f >> n;
    for (i = 1; i <= n; i++) {
        f >> v[i].x >> v[i].y;
    }
    g << fixed << setprecision(2);
    sort(v+1, v+n+1);
    v[n+1].x = v[1].x;
    v[n+1].y = v[1].y;
    if (n <= 2) {
        g << 0.00;
        f.close();
        g.close();
        return 0;
    }
    lowerHull.push_back(1);
    lowerHull.push_back(2);
    j = 1;
    for (i = 3; i <= n; i++) {
        while (j >= 1 && getOrientation(v[lowerHull[j-1]], v[lowerHull[j]], v[i]) != CCW) {
            lowerHull.pop_back();
            j--;
        }
        lowerHull.push_back(i);
        j++;
    }
    lowerHull.pop_back();
    upperHull.push_back(n);
    upperHull.push_back(n-1);
    j = 1;
    for (i = n-2; i >= 1; i--) {
        while (j >= 1 && getOrientation(v[upperHull[j-1]], v[upperHull[j]], v[i]) != CCW) {
            upperHull.pop_back();
            j--;
        }
        upperHull.push_back(i);
        j++;
    }
    upperHull.pop_back();
    for (j = 0; j < upperHull.size(); j++) {
        lowerHull.push_back(upperHull[j]);
    }
    upperHull.clear();
    if (lowerHull.size() <= 2) {
        g << 0.00;
        f.close();
        g.close();
        return 0;
    }
    j = lowerHull.size();
    for (i = 0; i <= j+1; i++) {
        lowerHull.push_back(lowerHull[i]);
    }
    i = 0;
    j = k = l = 1;
    /// i = o latura a sublerului/dreptunghiului
    /// j = opus lui i
    /// k = latura din dreapta a dreptunghiului
    /// l = opus lui k
    finalarea = 0.0;
    setarea = false;
    for (i = 0; i < lowerHull.size() / 2 - 1; i++) {
        area = getTriangleArea(v[lowerHull[i]], v[lowerHull[i+1]], v[lowerHull[j]]);
        while ((area2 = getTriangleArea(v[lowerHull[i]], v[lowerHull[i+1]], v[lowerHull[j+1]])) > area) {
            area = area2;
            j++;
        }
        while (getRightAngleOffset(v[lowerHull[i]], v[lowerHull[i+1]], v[lowerHull[k]], v[lowerHull[k+1]]) == LESS90)
            k++;
        if (l < j)
            l = j;
        while (getRightAngleOffset(v[lowerHull[i+1]], v[lowerHull[i]], v[lowerHull[l]], v[lowerHull[l+1]]) == LESS90)
            l++;

        aux.x = v[lowerHull[i+1]].x - v[lowerHull[i]].x;
        aux.y = v[lowerHull[i+1]].y - v[lowerHull[i]].y;
        aux.rotateCCW();
        aux.translate(v[lowerHull[l]].x, v[lowerHull[l]].y);

        rect1 = getTriangleArea(v[lowerHull[i]], v[lowerHull[i+1]], v[lowerHull[j]]);
        rect2 = getTriangleArea(v[lowerHull[k]], aux, v[lowerHull[l]]);
        rectdiv = getDist(v[lowerHull[i]], v[lowerHull[i+1]]);
        decarea = (((long double)(rect1)) / rectdiv) * rect2;
        if (decarea < finalarea || !setarea) {
            finalarea = decarea;
            setarea = true;
        }
    }
    g << finalarea;
    f.close();
    g.close();
    return 0;
}