Cod sursa(job #1211776)

Utilizator andreiiiiPopa Andrei andreiiii Data 23 iulie 2014 12:05:58
Problema Rubarba Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.27 kb
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cmath>
#include <vector>

using namespace std;

const int Nmax = 100005;
const double Eps = 1e-12;

class Point {
public:
    double x, y;

    Point(const double _x = 0, const double _y = 0):
        x(_x),
        y(_y) {}

    bool operator<(const Point &other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }

    bool operator==(const Point &other) const {
        return (x == other.x && y == other.y);
    }
};

bitset<Nmax> Used;

inline double getsign(double x)
{
    return (x < 0 ? -1: 1);
}

double CrossProduct(const Point o, const Point a, const Point b)
{
    return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}

double Dist(const Point a, const Point b)
{
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

double Dist(const Point o, const Point a, const Point b)
{
    return CrossProduct(o, a, b) / sqrt(Dist(a, b));
}

Point Rotate90(Point a, Point o)
{
    Point ret;

    ret.x = o.x - (a.y - o.y);
    ret.y = o.y + (a.x - o.x);

    return ret;
}

vector<Point> ConvexHull(const vector<Point>& Points)
{
    vector<int> UsedPoints(2, 0);
    UsedPoints[1] = 1;
    Used[1] = 1;

    for (int i = 2; i < int(Points.size()); i++)
    {
        while (UsedPoints.size() > 1U && CrossProduct(Points[UsedPoints[UsedPoints.size() - 2]], Points[UsedPoints.back()], Points[i]) < Eps)
        {
            Used[UsedPoints.back()] = 0;
            UsedPoints.pop_back();
        }

        Used[i] = 1;
        UsedPoints.push_back(i);
    }

    for (int i = Points.size() - 2; i >= 0; i--)
    {
        if (!Used[i])
        {
            while (UsedPoints.size() > 1U && CrossProduct(Points[UsedPoints[UsedPoints.size() - 2]], Points[UsedPoints.back()], Points[i]) < Eps)
            {
                Used[UsedPoints.back()] = 0;
                UsedPoints.pop_back();
            }

            Used[i] = 1;
            UsedPoints.push_back(i);
        }
    }

    vector<Point> Hull(UsedPoints.size() - 1);

    for (int i = 0; i < int(Hull.size()); i++)
        Hull[i] = Points[UsedPoints[i]];

    return Hull;
}

double Solve(const vector<Point>& Polygon)
{
    const int N = Polygon.size();

    double MinArea = 1e17;
    int up = 1, left = 0, right = 1;

    for (int i = 0; i < N; i++)
    {
        Point a = Polygon[i], b = Polygon[i < N - 1 ? i + 1: 0];

        for (int prev = up ? up - 1: N - 1; Dist(Polygon[prev], a, b) - Dist(Polygon[up], a, b) > -Eps; up = prev, prev = up ? up - 1: N - 1);
        for (int next = up < N - 1 ? up + 1: 0; Dist(Polygon[next], a, b) - Dist(Polygon[up], a, b) > -Eps; up = next, next = up < N - 1 ? up + 1: 0);

        Point aRotated = Rotate90(a, b);

        for (int prev = left ? left - 1: N - 1; Dist(Polygon[left], b, aRotated) - Dist(Polygon[prev], b, aRotated) > -Eps; left = prev, prev = left ? left - 1: N - 1);
        for (int next = left < N - 1 ? left + 1: 0; Dist(Polygon[left], b, aRotated) - Dist(Polygon[next], b, aRotated) > -Eps; left = next, next = left < N - 1 ? left + 1: 0);

        for (int prev = right ? right - 1: N - 1; Dist(Polygon[prev], b, aRotated) - Dist(Polygon[right], b, aRotated) > -Eps; right = prev, prev = right ? right - 1: N - 1);
        for (int next = right < N - 1 ? right + 1: 0; Dist(Polygon[next], b, aRotated) - Dist(Polygon[right], b, aRotated) > -Eps; right = next, next = right < N - 1 ? right + 1: 0);

        double dist1 = Dist(Polygon[up], a, b);
        double dist2 = Dist(Polygon[right], b, aRotated) - Dist(Polygon[left], b, aRotated);

        MinArea = min(MinArea, dist1 * dist2);
    }

    return MinArea;
}

void Write(const vector<Point> &Polygon)
{
    for (const Point p: Polygon)
        printf("%lf %lf\n", p.x, p.y);
}

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

    int N;
    scanf("%d", &N);

    vector<Point> Polygon(N);
    for (int i = 0; i < N; i++)
        scanf("%lf%lf", &Polygon[i].x, &Polygon[i].y);

    sort(Polygon.begin(), Polygon.end());
    Polygon.erase(unique(Polygon.begin(), Polygon.end()), Polygon.end());

    if (Polygon.size() < 3U)
    {
        printf("0.00\n");
        return 0;
    }

    Polygon = ConvexHull(Polygon);
    N = Polygon.size();

    //Write(Polygon);

    printf("%.3lf\n", Solve(Polygon));
}