Cod sursa(job #1336847)

Utilizator retrogradLucian Bicsi retrograd Data 8 februarie 2015 12:28:16
Problema Rubarba Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 kb
#include<fstream>
#include<limits>
#include<cmath>

typedef double var;
using namespace std;

ifstream fin("rubarba.in");
ofstream fout("rubarba.out");

const var INF = numeric_limits<double>::max();
const int MAXN = 100001;

struct Point {
    var x, y;
    Point(var a, var b) {
        x = a;
        y = b;
    }
    Point() {}
};

Point POINTS[MAXN],
p_sus, p_st, p_dr, p_jos;


inline var unghi_sus(Point p) {
    if(p.x == p_sus.x) return INF;
    return -(p.y - p_sus.y) / (p.x - p_sus.x);
}

inline var unghi_dr(Point p) {
    if(p.y == p_dr.y) return INF;
    return (p.x - p_dr.x) / (p.y - p_dr.y);
}

inline var unghi_jos(Point p) {
    if(p.x == p_jos.x) return INF;
    return -(p.y - p_jos.y) / (p.x - p_jos.x);
}

inline var unghi_st(Point p) {
    if(p.y == p_st.y) return INF;
    return (p.x - p_st.x) / (p.y - p_st.y);
}



int main() {
    int n;
    var x, y;
    fin>>n;
    p_st.x = INF;
    p_dr.x = -INF;
    p_sus.y = -INF;
    p_jos.y = INF;
    for(int i=1; i<=n; i++) {
        fin>>x>>y;
        POINTS[i] = Point(x, y);
        if(x < p_st.x) p_st = POINTS[i];
        if(y < p_jos.y) p_jos = POINTS[i];
        if(x > p_dr.x) p_dr = POINTS[i];
        if(y > p_sus.y) p_sus = POINTS[i];
    }

    var u, min_u = INF;
    var DELTA1, DELTA2, S1, S2;

    for(int i=1; i<=n; i++) {
        Point p = POINTS[i];

        u = unghi_st(p);
        if(u != INF and u > 0 and u < min_u) min_u = u;
        u = unghi_sus(p);
        if(u != INF and u > 0 and u < min_u) min_u = u;
        u = unghi_dr(p);
        if(u != INF and u > 0 and u < min_u) min_u = u;
        u = unghi_jos(p);
        if(u != INF and u > 0 and u < min_u) min_u = u;
    }

    u = min_u;
    DELTA1 = ( (p_dr.x - p_st.x) - (p_dr.y - p_st.y) * u ) / sqrt(1 + u * u);
    DELTA2 = ( (p_sus.y - p_jos.y) + (p_sus.x - p_jos.x) * u) / sqrt(1 + u * u);
    S1 = DELTA1 * DELTA2;



    min_u = INF;
    for(int i=1; i<=n; i++) {
        Point p = POINTS[i];

        u = -unghi_st(p);
        if(u != INF and u > 0 and u < min_u) min_u = u;
        u = -unghi_sus(p);
        if(u != INF and u > 0 and u < min_u) min_u = u;
        u = -unghi_dr(p);
        if(u != INF and u > 0 and u < min_u) min_u = u;
        u = -unghi_jos(p);
        if(u != INF and u > 0 and u < min_u) min_u = u;
    }

    u = min_u;
    DELTA1 = ( (p_dr.x - p_st.x) + (p_dr.y - p_st.y) * u ) * (1 / sqrt(1 + u * u));
    DELTA2 = ( (p_sus.y - p_jos.y) - (p_sus.x - p_jos.x) * u) * (1 / sqrt(1 + u * u));
    S2 = DELTA1 * DELTA2;

    fout << min(S1, S2);



    return 0;
}