Cod sursa(job #1212413)

Utilizator andreiiiiPopa Andrei andreiiii Data 24 iulie 2014 16:57:59
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.34 kb
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cassert>
#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);
    }
};


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;

    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)
            UsedPoints.pop_back();

        UsedPoints.push_back(i);
    }

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

    for (int i = 0; i < int(Hull.size()); i++)
        Hull[i] = Points[UsedPoints[i]];
    //reverse(Hull.begin(), Hull.end());

    return Hull;
}

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

    double MinArea = 1e18;
    int up = 1, left = 1, right = 1;

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

        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);
        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);

        Point aRotated = Rotate90(a, b);

        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 = 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 = 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);
        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);

        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);
}


Point Or;
struct comp {
    bool operator() (const Point &a, const Point &b) const {
        double p1 = (a.x != Or.x) ? ((a.y - Or.y) / (a.x - Or.x)): 1e18;
        double p2 = (b.x != Or.x) ? ((b.y - Or.y) / (b.x - Or.x)): 1e18;

        if (abs(p1 - p2) < Eps)
            return Dist(Or, a) < Dist(Or, b);

        return p1 < p2;
    }
};

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);

        if (Polygon[i] < Polygon[0])
            swap(Polygon[i], Polygon[0]);
    }

    Or = Polygon[0];
    sort(Polygon.begin() + 1, Polygon.end(), comp());
    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);

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


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