Cod sursa(job #1863551)

Utilizator mariusn01Marius Nicoli mariusn01 Data 30 ianuarie 2017 23:25:58
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.45 kb
#include <fstream>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define DIM 100010
#define eps 1e-14

using namespace std;

struct punct {
    double x;
    double y;
    punct (double x, double y) {
        this->x = x;
        this->y = y;
    }
    punct () {
        this->x = 0;
        this->y = 0;
    }
};

punct p[DIM], s[DIM];
double minim = 1e14;
int n, k;

double det(const punct &a, const punct &b, const punct &c) {
    return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}

int zero(const punct &a, const punct &b, const punct &c) {
    double d = det(a, b, c);
    if (d <= eps && d >= -eps)
        return 1;
    return 0;
}

int zero(double x) {
    return (x >= -eps && x <= eps);
}

double patratDistantaPuncte(punct a, punct b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

int cmp( const punct &a, const punct &b  ) {
    double d = det(p[1], a, b);
    if (d <= eps && d >= -eps)
        return patratDistantaPuncte(p[1], a) > patratDistantaPuncte(p[1], b);
    return det(p[1], a, b) > 0;
}

inline int next(int i) {
    return (i==k?1:i+1);
}

inline int prev(int i) {
    return (i==1?k:i-1);
}

punct piciorPerpendiculara(punct a, punct b, punct c) {
    // piciorul perpendicularei din c pe dreapta ab
    if (zero(a.y - b.y)) {
        punct r(c.x, a.y);
        return r;
    }
    if (zero(a.x - b.x)) {
        punct r(a.x, c.y);
        return r;
    }

    double M = (b.y - a.y)/(b.x - a.x);
    double B1 = ( a.y * (b.x - a.x) - a.x * (b.y - a.y) ) / (b.x - a.x);
    double B2 = c.y + c.x/M;
    punct r;
    r.x = M * (B2 - B1) / (M*M + 1);
    r.y = M * r.x + B1;
    return r;
}

double distPunctDereapta(punct a, punct b, punct c) {
    double A= det(a, b, c);
    if (A < 0)
        A = -A;
    double D = patratDistantaPuncte(a, b);

    return A/sqrt(D);
}

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

    fin>>n;
    //double minim = 1000001;
    for (int i=1;i<=n;i++) {
        fin>>p[i].x>>p[i].y;
    }

    int poz = 1;
    for (int i=2;i<=n;i++) {
        if ( (p[i].y < p[poz].y) || ( zero(p[i].y - p[poz].y) && (p[i].x < p[poz].x) ) )
            poz = i;
    }

    punct aux = p[1];
    p[1] = p[poz];
    p[poz] = aux;

    for (int i=2;i<=n;i++) {
        p[i].x -= p[1].x;
        p[i].y -= p[1].y;
    }
    p[1].x = p[1].y = 0;

    sort(p+2, p+n+1, cmp);

    int i=3;
    while (zero(p[1], p[2], p[i]))
        i++;
    i--;
    int j=2;
    while (j<i) {
        aux = p[j];
        p[j] = p[i];
        p[i] = aux;
        j++;
        i--;
    }

    s[1] = p[1];
    s[2] = p[2];
    k = 2;
    for (int i=3; i<=n; i++) {
        while (k >= 2 && det(s[k-1], s[k], p[i]) <= 0  )
            k--;
        s[++k] = p[i];
    }

    int a = 2, b = 2, c = 2;
    punct ra, rn;
    for (int z=1;z<=k;z++) {
//        if (s[z].x == s[next(z)].x && s[z].y == s[next(z)].y)
//            continue;
        a = next(z);
        ra = piciorPerpendiculara(s[z], s[next(z)], s[a]);
        do {
            rn = piciorPerpendiculara(s[z], s[next(z)], s[next(a)]);
            if ( (rn.x-ra.x) * (ra.x-s[z].x) > 0 || (rn.y-ra.y) * (ra.y-s[z].y) > 0) {
                a = next(a);
                ra = rn;
            }
            else
                break;
        } while (1);
        punct r1 = ra;


        b = next(z);
        double da, dn;
        da = distPunctDereapta(s[z], s[next(z)], s[b]);
        do {
            dn = distPunctDereapta(s[z], s[next(z)], s[next(b)]);
            if (dn >= da) {
                b = next(b);
                da = dn;
            } else
                break;
        } while (1);

        c = z;
        ra = piciorPerpendiculara(s[z], s[next(z)], s[c]);
        do {
            rn = piciorPerpendiculara(s[z], s[next(z)], s[prev(c)]);
            if ( (ra.x-s[next(z)].x) * (rn.x - ra.x) > 0 || (ra.y-s[next(z)].y) * (rn.y - ra.y) > 0 ) {
                c = prev(c);
                ra = rn;
            }
            else
                break;
        } while (1);
        punct r2 = ra;

        if (sqrt(patratDistantaPuncte(r1, r2)) * distPunctDereapta(s[z], s[next(z)], s[b]) < minim) {
            minim = sqrt(patratDistantaPuncte(r1, r2)) * distPunctDereapta(s[z], s[next(z)], s[b]);
        }
    }

    fout<<setprecision(2)<<fixed<<minim;
    return 0;
}