Cod sursa(job #2650051)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 17 septembrie 2020 12:08:24
Problema Rubarba Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 7.37 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 100005


#define eps 0.000000001
#define INF 2000000000
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);
    }

    // rotate plane with angle
    static void rotate(vector<Point> &points, long double angle = 0){
        if (abs(angle) < eps){
            unsigned seed1 = chrono::system_clock::now().time_since_epoch().count();
            std::mt19937 generator(seed1);
            std::uniform_real_distribution<long double> distribution(0.0, 3.14);

            angle = distribution(generator);
        }

        for (auto &it : points){
            long double x = it.x * cos(angle) - it.y * sin(angle);
            long double y = it.x * sin(angle) + it.y * cos(angle);
            it = {x,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{
        if (abs(m-oth.m) < eps) return {INF,INF};
        long double x = (oth.b - b) / (m - oth.m);
        long double y = getY(x);
        return {x,y};
    }

    long double dist(Line &oth) const{
        if (abs(m-oth.m) >= eps) return 0;
        return abs(oth.b-b) / sqrt(m*m+1);
    }

    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;

bool _try(int aux, long double m, long double &d, int &savTop, Line bot, Line &top){
    Line l1 = Line(p[aux], m);
    if (l1.dist(bot) >= d){
        d = l1.dist(bot);
        savTop = aux;
        top = Line(p[savTop],m);
        return 1;
    }
    return 0;
}

void extend(int &savTop, int &savBot, long double m){
    Line top = Line(p[savTop], m);
    Line bot = Line(p[savBot], m);
    long double d = top.dist(bot);
    int ok = 1,aux;
    while (ok){
        ok = _try((savTop + 1) % p.size(), m, d, savTop, bot, top);
        //ok = _try((savTop - 1 + p.size()) % p.size(), m, d, savTop, bot, top);
        ok |= _try((savBot + 1) % p.size(), m, d, savBot, top,bot);
        //ok |= _try((savBot - 1 + p.size()) % p.size(), m, d, savBot, top, bot);
    }
}

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;

    Geom::rotate(p);
    p = c.getConvexHull(p);

    long double ans = 1e9;
    Line l(p[0],p[1]);
    long double mp = l.perpendicularAngle();
    long double m = l.m;

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

        extend(savTop, savBot, m);
        extend(savLeft, savRight, mp);

        top = Line(p[savTop], m);
        bot = Line(p[savBot], m);
        left = Line(p[savLeft], mp);
        right = Line(p[savRight], 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;
}