Cod sursa(job #2327513)

Utilizator MAXIMILLIANMUSOHYEAHYEAH MAXIMILLIANMUS Data 24 ianuarie 2019 19:17:40
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.33 kb
#include <bits/stdc++.h>
#define maxN 100002
#define e 1e-7
using namespace std;
 
FILE *fin = freopen("rubarba.in", "r", stdin);
FILE *fout = freopen("rubarba.out", "w", stdout);
 
int n;
struct Point
{
    double x, y;
    bool operator < (const Point &ot) const
    {
        if (fabs(x - ot.x) < e)
            return y < ot.y;
        return x < ot.x;
    }
};
struct Line
{
    double a, b, c;
 
    Line() {}
 
    Line(double _a, double _b, double _c)
    {
        a = _a;
        b = _b;
        c = _c;
    }
};
 
class Geometry
{
public :
    int N;
    Point *v;
    Geometry(int N);
    void readVertexes();
    double CCW(Point A, Point B, Point C)
    {
        return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
    }
    double dist(Point A, Point B)
    {
        return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
    }
    double Dist(Line l, Point A)
    {
        return l.a * A.x + l.b * A.y + l.c;
    }
    double Det(Point A, Point B, Point C)
    {
        return A.x * B.y
               + B.x * C.y
               + C.x * A.y
               - C.x * B.y
               - A.x * C.y
               - B.x * A.y;
    }
    double Area(Point A, Point B, Point C)
    {
        return fabs(Det(A, B, C)) / 2;
    }
    int nxt(int x)
    {
        if (x == N - 1)
            return 0;
        return x + 1;
    }
    void spLine(Line &l)
    {
        double coef = 1 / sqrt(l.a * l.a + l.b * l.b);
        l.a *= coef;
        l.b *= coef;
        l.c *= coef;
    }
    Line getLine(Point A, Point B)
    {
        Line l = {B.y - A.y, A.x - B.x, A.y * B.x - A.x * B.y};
        spLine(l);
        return l;
    }
    Line Perp(Line l, Point A)
    {
        Line lp;
        lp.a = -l.b;
        lp.b = l.a;
        lp.c = -lp.a * A.x - lp.b * A.y;
        spLine(lp);
        return lp;
    }
    void ConvexHull();
    double MinArea();
};
 
Geometry::Geometry(int n)
{
    this->N = n;
    v = new Point[n + 1];
}
void Geometry::readVertexes()
{
    for (int i = 0; i < N; ++ i)
        scanf("%lf %lf", &v[i].x, &v[i].y);
    if (N == 2)
    {
        printf("%.9lf\n", dist(v[0], v[1]));
        exit(0);
    }
}
void Geometry::ConvexHull()
{
    for(int i = 1; i < N; i++)
        if (v[i] < v[0]) swap(v[0], v[i]);
    sort(v + 1, v + N, [&](Point A, Point B)
    {
        return CCW(v[0], A, B) < 0;
    });
 
    vector < int > st;
    int stSize = 0;
    for (int i = 0; i < N; ++ i)
    {
        while (st.size() > 1 && CCW(v[st[stSize - 2]], v[st[stSize - 1]], v[i]) > -e)
        {
            st.pop_back();
            -- stSize;
        }
        st.push_back(i);
        ++ stSize;
    }
    for (int i = 0; i < stSize; ++ i)
        v[i] = v[st[i]]; /// st[i] >= i, V i = 0, N
    N = stSize;
}
 
double Geometry::MinArea()
{
    int p = 0, q = 1;
    Line L = getLine(v[p], v[q]), Lp = Perp(L, v[p]);
 
    double dx = Dist(L, v[0]), dy1, dy2;
    int p0 = 0, p1 = 0, p2 = 0;
    dy1 = dy2 = dx;
    dx = fabs(dx);
 
    for (int i = 0; i < N; ++ i)
    {
        double d = Dist(L, v[i]), D = Dist(Lp, v[i]);
        if (fabs(d) > dx)
        {
            p0 = i;
            dx = fabs(d);
        }
        if (D < dy1)
        {
            dy1 = D;
            p1 = i;
        }
        if (D > dy2)
        {
            dy2 = D;
            p2 = i;
        }
    }
 
    double ans = dx * (dy2 - dy1);
    for (; nxt(p) < N - 1;)
    {
        p = nxt(p);
        q = nxt(q);
        L = getLine(v[p], v[q]);
        Lp = Perp(L, v[p]);
        dx = fabs(Dist(L, v[p0]));
        dy1 = Dist(Lp, v[p1]);
        dy2 = Dist(Lp, v[p2]);
        while (fabs(Dist(L, v[nxt(p0)])) > dx)
        {
            dx = fabs(Dist(L, v[nxt(p0)]));
            p0 = nxt(p0);
        }
        while (Dist(Lp, v[nxt(p1)]) < dy1)
        {
            dy1 = Dist(Lp, v[nxt(p1)]);
            p1 = nxt(p1);
        }
        while (Dist(Lp, v[nxt(p2)]) > dy2)
        {
            dy2 = Dist(Lp, v[nxt(p2)]);
            p2 = nxt(p2);
        }
        ans = min(ans, dx * (dy2 - dy1));
    }
    return ans;
}
 
int main()
{
    scanf("%d", &n);
    Geometry P(n);
    P.readVertexes();
    P.ConvexHull();
    printf("%.9lf\n", P.MinArea());
    return 0;
}