Cod sursa(job #2649768)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 16 septembrie 2020 12:11:19
Problema Rubarba Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.18 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 100005


#define eps 0.000000001
class Point{
public:
    long double x, y;
    Point() : x(0), y(0){}
    Point(long double _x, long double _y) : x(_x), y(_y){}

    bool operator==(const Point &oth) const {return x == oth.x && y == oth.y;}
    bool operator< (const Point &oth) const {return x == oth.x ? y < oth.y : x < oth.x;}

    long double dist(Point B){
        return sqrt((x - B.x) * (x - B.x) + (y - B.y) * (y - B.y));
    }

    friend ostream &operator<<( ostream &output, const Point &P ) {
        output << P.x << " " << P.y;
        return output;
    }

    friend istream &operator>>( istream &input, Point &P ) {
         input >> P.x >> P.y;
         return input;
    }
};

class Geom{
public:
    static long double det(Point A, Point B, Point C){
         return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
    }
};


class ConvexHull{
private:
    static Point bst;

    static bool comp(Point &A, Point &B){
        if (B == bst) return false;
        int x = Geom::det(bst,A,B);
        if (abs(x) < eps) return bst.dist(A) < bst.dist(B);
        return x < 0;
    }

public:

    vector<Point> getConvexHull(vector<Point> points){
        if (points.size() <= 1) return points;

        bst = points[0];
        for (auto &it : points) bst = min(bst, it);

        sort(points.begin(),points.end(),comp);

        vector<Point> H({points[0], points[1]});
        for (int i=2;i<(int)points.size();i++){
            while (H.size() >= 2 && (Geom::det(H[H.size() - 2], H.back(), points[i]) > 0 ||
                   (Geom::det(H[H.size() - 2], H.back(), points[i]) == 0 &&
                    H[H.size() - 2].dist(H.back()) < H[H.size() - 2].dist(points[i])))){
                        H.pop_back();
                   }
            H.push_back(points[i]);
        }
        return H;
    }
};
Point ConvexHull::bst;

class Line{
public:
    long double m, b;

    Line() : m(0), b(0){}
    // line AB
    Line(Point &A, Point &B){
        m = (A.y - B.y) / (A.x - B.x);
        b = A.y - m * A.x;
    }

    // line with angle alfa with point A
    Line(Point &A, long double m){
        this->m = m;
        b = A.y - m * A.x;
    }

    // ax+by+c
    Line(long double a, long double b, long double c){
        m = -a / b;
        this->b = -c / b;
    }

    Line(long double m, long double b){
        this->m = m;
        this->b = b;
    }

    long double getX(long double y) const{
        return (y - b) / m;
    }

    long double getY(long double x) const{
        return m * x + b;
    }

    long double perpendicularAngle(){
        return -1 / m;
    }

    Point intersect(Line &oth) const{
        long double x = (oth.b - b) / (m - oth.m);
        long double y = getY(x);
        return {x,y};
    }

    bool isParalel(Line &oth){
        return abs(m - oth.m) < eps;
    }
};

class Rectangle{
private:
    void sortTrigonom(Point &A, Point &B, Point &C, Point &D){
        ConvexHull c = ConvexHull();
        vector<Point> ans = c.getConvexHull({A,B,C,D});
        A = ans[0]; B = ans[1]; C = ans[2]; D = ans[3];
    }


public:
    Point A,B,C,D;

    Rectangle(Point &A, Point &B, Point &C, Point &D){
        this->A = A; this->B = B; this->C = C; this->D = D;
        sortTrigonom(this->A,this->B,this->C,this->D);
    }

    Rectangle(Line &L1, Line &L2, Line &L3, Line &L4){
        if (L1.isParalel(L2)) swap(L2, L3);
        if (L1.isParalel(L4)) swap(L3, L4);
        A = L1.intersect(L2);
        B = L2.intersect(L3);
        C = L3.intersect(L4);
        D = L4.intersect(L1);
        sortTrigonom(A,B,C,D);
    }

    long double area(){
        return A.dist(B) * B.dist(C);
    }

    long double perimeter(){
        // to do
    }
};

int n;
vector<Point> p;

int main()
{
    freopen("rubarba.in","r",stdin);
    freopen("rubarba.out","w",stdout);

    scanf("%d", &n);
    for (int i=1;i<=n;i++){
        int x,y;
        scanf("%d%d", &x, &y);
        p.push_back({(long double)x,(long double)y});
    }

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

    ConvexHull c;

    p = c.getConvexHull(p);

    long double ans = 1e9;
    p.push_back(p[0]);
    for (int i=0;i<n;i++){
        Line l(p[i],p[i+1]);
        long double mp = l.perpendicularAngle();
        long double m = l.m;
        Line top(p[i],p[i+1]), bot(p[i],p[i+1]), left(p[0],mp), right(p[0],mp);
        for (auto &it : p){
            if (top.getX(0) < Line(it,m).getX(0)) top = Line(it, m);
            if (bot.getX(0) > Line(it,m).getX(0)) bot = Line(it, m);
            if (left.getX(0) < Line(it,mp).getX(0)) left = Line(it, mp);
            if (right.getX(0) > Line(it,mp).getX(0)) right = Line(it, mp);
        }

        Rectangle r(top,left,bot,right);

        ans = min(ans, r.area());
       // cout << r.area() << ' ' << p[i].x << ' ' << p[i].y << ' ' << p[i+1].x << ' ' << p[i+1].y << '\n';
       // cout << r.A.x << ' ' << r.A.y << ' ' << r.C.x << ' ' << r.C.y << '\n';
    }

    cout << fixed << setprecision(2) << ans << '\n';

    return 0;
}