Cod sursa(job #938351)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 12 aprilie 2013 14:05:21
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 7.56 kb
#include <stdlib.h>
#include <fstream>
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <string.h>
#include <iomanip>
#include <time.h>
#include <list>
#include <algorithm>
#include <math.h>
#include <assert.h>
using namespace std;


const string file = "rubarba";

const string infile = file + ".in";
const string outfile = file + ".out";

struct Point
{

    Point()
    {

    }

    Point(int x, int y)
    {
        this->x = x;
        this->y = y;
    }
    int x;
    int y;
};


vector<Point> points;
vector<Point> convexHull;
int N;
long double minArea;

long long CrossProduct(const Point& s, const Point& p1, const Point& p2)
{
    long long result = 1LL * (p1.x - s.x)*(p2.y - s.y) - 1LL * (p1.y - s.y) * (p2.x - s.x);
    return result;
}


Point Substract(const Point&a, const Point &b)
{
    int px = b.x - a.x;
    int py = b.y - a.y;

    return Point(px, py);
}

long double Distance(const Point&a)
{
    return sqrt((long double)(a.x * a.x) + a.y * a.y);
}


bool SortPredicate(const Point& a, const Point& b)
{

    long double val1 = 1.0*(a.y - points[0].y )/(1.0*a.x - points[0].x);
    long double val2 = 1.0*(b.y - points[0].y )/(1.0*b.x - points[0].x);

    if(val1 < val2)
    {
        return true;
    }

    if(val1 > val2)
    {
        return false;
    }

    return Distance(Substract(a, points[0])) < Distance(Substract(b, points[0]));


}

void citire()
{
    ifstream fin(infile.c_str());

    fin >> N;
    points.reserve(N);
    int minI = 0;
    for(int i = 0 ; i < N; i++)
    {
        int x, y;
        fin >> x >> y;
        points.push_back(Point(x, y));

        if(points[minI].x > x)
        {
            minI = i;
        }
        else if(points[minI].x == x)
        {
            minI = points[minI].y > y ? i : minI;
        }

    }

    swap(points[0], points[minI]);

    fin.close();
}

void GrahamScan()
{
    sort(points.begin() + 1, points.end(), SortPredicate);
    convexHull.reserve(N);
    for(int i = 0; i < N; i++)
    {
        while(convexHull.size() >= 2 && CrossProduct(convexHull[convexHull.size() - 2], convexHull[convexHull.size() - 1], points[i]) <= 0LL)
        {
            convexHull.pop_back();
        }

        convexHull.push_back(points[i]);
    }

}

struct PointD
{
    long double x;
    long double y;

    PointD()
    {

    }

    PointD(long double x, long double y)
    {
        this->x = x;
        this->y = y;
    }
};


struct LineD
{
    LineD()
    {

    }

    LineD(const Point& p1, const Point& p2)
    {
        this->slope = 1.0 *(p2.y - p1.y) / (p2.x - p1.x);
        this->c = p1.y - p1.x * slope;
    }

    LineD(const PointD& p1, long double slope)
    {
        this->c = p1.y - p1.x * slope;
        this->slope = slope;
    }


    LineD(const Point& p1, long double slope)
    {
        this->c = p1.y - p1.x * slope;
        this->slope = slope;
    }

    long double slope;
    long double c;
};


long double Distance(const LineD & line, const Point& p1 )
{
    long double s = p1.y - line.slope * p1.x - line.c;
    return s / sqrt(1 + line.slope * line.slope);
}

long double ProdusScalar(const PointD& p1, const PointD& p2)
{
    return p1.x * p2.x + p1.y * p2.y;
}

long double Norma(const PointD& p)
{
    return sqrt(p.x * p.x + p.y * p.y);
}


PointD Translate(const PointD& p1, const PointD& p2)
{
    return PointD(p2.x - p1.x, p2.y - p1.y);
}

void RotateClockwise(PointD& p, long double sine, long double cosine)
{
    long double x = p.x;
    long double y = p.y;
    p.x = x * cosine + y * sine;
    p.y =  - x * sine + y * cosine;
}

int Next(int i)
{
    return i == 0 ? convexHull.size() - 1 : i - 1;
}

int Prev(int i)
{
    return i == convexHull.size() - 1 ? 0 : i + 1;
}


struct Calliper
{
    int p;
    PointD v;
    bool marked;
    long double nextAngle;
    void rotate(long double sine, long double cosine)
    {
        marked = false;
        if(cosine == nextAngle)
        {
            marked = true;
            p = Next(p);
        }
        RotateClockwise(v, sine, cosine);
    }

    long double getNextAngle()
    {
        Point &p1 = convexHull[p];
        Point &p2 = convexHull[Next(p)];

        Point translated = Substract(p1, p2);
        PointD t(translated.x, translated.y);

        long double ang = ProdusScalar(v, t) / Norma(t);
        nextAngle = ang;
        return ang;
    }

};


Calliper cal[4];


void initCallipers()
{
    int xMin = 0;
    int xMax = 0;
    int yMin = 0;
    int yMax = 0;

    for(unsigned int i = 0; i < convexHull.size(); i++)
    {
        int currentPoint = i;

        xMin = convexHull[currentPoint].x < convexHull[xMin].x ? currentPoint : xMin;
        xMax = convexHull[currentPoint].x > convexHull[xMax].x ? currentPoint : xMax;

        yMin = convexHull[currentPoint].y < convexHull[yMin].y ? currentPoint : yMin;
        yMax = convexHull[currentPoint].y > convexHull[yMax].y ? currentPoint : yMax;

    }

    long double dXdif = (convexHull[xMax].x - convexHull[xMin].x);
    long double dYdif = (convexHull[yMax].y - convexHull[yMin].y);
    minArea = dXdif * dYdif;

    cal[0].v = PointD(0, 1); cal[0].p = xMin;
    cal[1].v = PointD(0, -1); cal[1].p = xMax;
    cal[2].v = PointD(-1, 0); cal[2].p = yMin;
    cal[3].v = PointD(1, 0); cal[3].p = yMax;

}

const long double INF = 10000000000000000000.00L;

long double GetSlope(const Point& p1, const Point& p2)
{
    if(p1.x == p2.x)
    {
        return INF;
    }

    return 1.0L * (p1.y - p2.y) / (p1.x - p2.x);

}

void CalculateArea()
{

    LineD lines[2];
    Point l[2];

    for(int i = 0; i <4; i++)
    {
        if(cal[i].marked == true)
        {
            l[0] = convexHull[cal[i].p];
            l[1] = convexHull[Prev(cal[i].p)];
        }
    }

    long double slope1 = GetSlope(l[0], l[1]);
    if(slope1 == INF || fabs(slope1) <= 0.000000001L ) return;
    long double slope2 = -1.0L / slope1;

    lines[0] = LineD(l[0], slope1);
    lines[1] = LineD(PointD((1.0L * l[0].x - l[1].x)/ 2.0L, (1.0L * l[0].y - l[1].y)/ 2.0L), slope2);

    long double up = 0;
    long double left = -INF;
    long double right = INF;

    for(int i = 0; i < 4; i++)
    {

        long double d;

        d =  fabs(Distance(lines[0], convexHull[cal[i].p]));
        up = max(up, d);

        d = Distance(lines[1], convexHull[cal[i].p]);

        left = max(left, d);
        right = min(right, d);

    }

    long double area = 0;
    area = up * (left - right);
    minArea = min(area, minArea);

}

void RotatingCallipers()
{
    if(convexHull.size() <= 2)
    {
        minArea = 0;
        return;
    }

    initCallipers();
    PointD x(0, 1);


    while(ProdusScalar(x, cal[0].v) >= -0.0001L)
    {

        long double minAngle = -1;

        for(int i = 0; i < 4; i++)
        {
            minAngle = max(minAngle, cal[i].getNextAngle());
        }

        long double sine = sqrt(1.0L - minAngle * minAngle);


        for(int i = 0; i < 4; i++)
        {
            cal[i].rotate(sine, minAngle);
        }

        CalculateArea();

    }

}


void solve()
{
    GrahamScan();
    RotatingCallipers();
}

void afisare()
{
    ofstream fout(outfile.c_str());

    fout << fixed << setprecision(2) << minArea << "\n";

    fout.close();
}


int main()
{
    citire();
    solve();
    afisare();
}