Cod sursa(job #1386915)

Utilizator ericptsStavarache Petru Eric ericpts Data 13 martie 2015 15:03:44
Problema Rubarba Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.46 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <iomanip>

const int MAX_N = 100000 + 10;
typedef long double ldouble;
const ldouble PI = 3.1415926535897932384626433832795;
const ldouble INF = (1LL << 62) - 1;
const ldouble EPS = 1e-9;



template<class T>
T abs(T a) {
    if(a < 0)
        return -a;
    else
        return a;
}

struct point {
    int x, y;
};

int n;
point v[MAX_N];

long long ccw(const point &A, const point &B, const point &C) {
    const long long x2 = C.x - B.x,
                    y2 = C.y - B.y,
                    x1 = B.x - A.x,
                    y1 = B.y - A.y;

    return x1 * y2 - x2 * y1;
}

//ccw < 0 => o ia la dreapta
//ccw > 0 => o ia la stanga

// CONVEX HULL

bool comp(const point &A, const point &B) {
    return ccw(v[1], A, B) > 0;
}


int ST[MAX_N];
int lv;

point aux[MAX_N];

void convexHull() {
    int st = 1;

    for(int i = 2 ; i <= n ; ++i) {
        if( (v[i].x < v[st].x) || (v[i].x == v[st].x && v[i].y < v[st].y) )
            st = i;
    }
    std::swap(v[st], v[1]);

    std::sort(v + 2, v + n + 1, comp);

    ST[1] = 1;
    ST[2] = 2;
    lv = 2;

    for(int i = 3 ; i <= n ; ++i) {

        while(lv >= 2 && ccw(v[ST[lv - 1]], v[ST[lv]], v[i]) < 0)
            --lv;
        ST[++lv] = i;
    }

    n = lv;
    for(int i = 1 ; i <= n ; ++i){
        aux[i] = v[ST[i]];
    }

    for(int i = 1 ; i <= n ; ++i)
        v[i] = aux[i];
}

//---------------------------- END CONVEX HULL





struct vector{
    ldouble x, y;

    vector(ldouble x, ldouble y):
        x(x),
        y(y) {}

    vector(point &A):
        x(A.x),
        y(A.y){}

    vector():
        x(0),
        y(0){}

    vector operator-(const vector &A) {
        vector ret = *this;
        ret.x -= A.x;
        ret.y -= A.y;
        return ret;
    }

    const inline ldouble len() {
        return sqrt(x * x + y * y);
    }
};

const ldouble dot(const ldouble x1, const ldouble x2, const ldouble y1, const ldouble y2) {
    return x1 * x2 + y1 * y2;
}

const ldouble dot(const vector &A, const vector &B) {
    return dot(A.x, B.x, A.y, B.y);
}

const ldouble angle(vector A, vector B) {
    const ldouble cos = dot(A, B) / (A.len() * B.len());
    return std::acos(cos);
}


struct caliper {
    ldouble x, y;
    //the components of the vector
    int sup;
    //the support point

    caliper(ldouble x, ldouble y, int sup):
        x(x),
        y(y),
        sup(sup){}

    caliper():
        x(0),
        y(0),
        sup(0){}




    vector getVector() {
        return vector(x, y);
    }

    ldouble nextAngle() {
        int next = sup + 1;
        if(next == n + 1)
            next = 1;

        vector P1 = vector(v[sup]),
               P2 = vector(v[next]);

        vector P = P2 - P1;

        return angle(getVector(), P);
    }

    void advancePoint() {
        ++sup;
        if(sup == n + 1)
            sup = 1;
    }

    void rotate(const ldouble cs, const ldouble sn) {
        const ldouble nx = x * cs - y * sn;
        const ldouble ny = x * sn + y * cs;

        x = nx;
        y = ny;
    }

    void rotate(const ldouble theta) {
        if(abs(theta - nextAngle()) <= EPS)
            advancePoint();
        rotate(cos(theta), sin(theta));
    }
};

caliper cal[4];
ldouble len[4];

ldouble area = INF;


void rotate(const ldouble theta) {
    for(int i = 0 ; i < 4 ; ++i)
        cal[i].rotate(theta);
}

void check() {

    for(int i = 0 ; i < 4 ; ++i)
        len[i] = 0;

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

        //solves the equation P1 + aV1 = P2 + aV2

        vector P1 = vector( v[cal[i].sup] ),
               P2 = vector( v[cal[j].sup] );

        vector P12 = P1 - P2;
        vector P21 = P2 - P1;

        vector V1 = cal[i].getVector();
        vector V2 = cal[j].getVector();

        const ldouble a = dot(P21, V1) / dot(V1, V1);
        const ldouble b = dot(P12, V2) / dot(V2, V2);

        len[i] += a;
        len[j] += -b;
    }

    ldouble now = 0;

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

        if(len[i] * len[j] > now)
            now = len[i] * len[j];
    }

    if(now < area)
        area = now;
}

int main() {
    std::ifstream in("rubarba.in");
    in >> n;
    for(int i = 1 ; i <= n ; ++i) {
        in >> v[i].x >> v[i].y;
    }
    convexHull();

    int xmin = 1, ymin = 1, xmax = 1, ymax = 1;

    for(int i = 1 ; i <= n ; ++i) {
        if(v[i].x < v[xmin].x)
            xmin = i;
        if(v[i].y < v[ymin].y)
            ymin = i;

        if(v[i].x > v[xmax].x)
            xmax = i;
        if(v[i].y > v[ymax].y)
            ymax = i;
    }

    cal[0] = caliper(1,  0, ymin);
    cal[1] = caliper(0,  1, xmax);
    cal[2] = caliper(-1, 0, ymax);
    cal[3] = caliper(0, -1, xmin);

    ldouble rot = 0;

    while(rot <= PI) {
        check();
        ldouble next = INF;
        for(int i = 0 ; i < 4 ; ++i) {
            ldouble now = cal[i].nextAngle();
            if(now < next)
                next = now;
        }
        rotate(next);
        rot += next;
    }
    check();

    std::ofstream out("rubarba.out");
    out.precision(5);

    out << area << "\n";
    out.close();

    return 0;
}