Cod sursa(job #821832)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 22 noiembrie 2012 18:26:15
Problema Rubarba Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.03 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<double, double> Point;

const int MaxN = 10005;
const double oo = 1e13;
const double Eps = 1e-12;

Point P[MaxN];
int N;
double Solution;

inline int Sign(Point P1, Point P2, Point P3) {
    return P1.x*P2.y + P2.x*P3.y + P3.x*P1.y - P1.y*P2.x - P2.y*P3.x - P3.y*P1.x;
}

void ConvexHull() {
    int Hull[MaxN], K = 0; memset(Hull, 0, sizeof(Hull));
    bool Used[MaxN]; memset(Used, 0, sizeof(Used));
    sort(P+1, P+N+1);
    Hull[++K] = 1;
    for (int i = 2, p = 1; i > 0; i += (p = (i == N ? -p : p))) {
        if (Used[i])
            continue;
        while (K > 1 && Sign(P[Hull[K-1]], P[Hull[K]], P[i]) <= Eps)
            Used[Hull[K--]] = false;
        Used[Hull[++K] = i] = true;
    }
    Point NewP[MaxN];
    for (int i = 1; i <= K; ++i)
        NewP[i] = P[Hull[i]];
    N = K-1;
    for (int i = 1; i <= N+1; ++i)
        P[i] = NewP[i];
}

inline void GetEquation(Point P1, Point P2, double &m, double &n) {
    m = (P2.y - P1.y)/(P2.x - P1.x);
    n = P1.y - m*P1.x;
}

inline Point Project(Point P1, Point P2, Point Q) {
    if (P1.x == P2.x)
        return Point(P1.x, Q.y);
    if (P1.y == P2.y)
        return Point(Q.x, P1.y);
    double m1, n1; GetEquation(P1, P2, m1, n1);
    double m2 = -1.0/m1, n2 = Q.y + 1.0/m1*Q.x;
    Point I;
    I.x = (n2 - n1)/(m1 - m2);
    I.y = m1*I.x + n1;
    return I;
}

inline double Distance(Point P1, Point P2) {
    return sqrt((P1.x - P2.x)*(P1.x - P2.x) + (P1.y - P2.y)*(P1.y - P2.y));
}

inline double LineDist(Point P1, Point P2, Point Q) {
    double m, n; GetEquation(P1, P2, m, n);
    double a = m, b = -1, c = n;
    return abs(a*Q.x + b*Q.y + c)/sqrt(a*a + b*b);
}

inline int Next(int X) {
    return X == N ? 1 : X+1;
}

void Solve() {
    ConvexHull();
    Solution = oo;
    int l = 1, r = 1;
    for (int i = 2; i <= N; ++i) {
        if (Project(P[1], P[2], P[l]) > Project(P[1], P[2], P[i]))
            l = i;
        if (Project(P[1], P[2], P[r]) < Project(P[1], P[2], P[i]))
            r = i;
    }
    for (int i = 1, h = 3; i <= N; ++i) {
        for (; Next(h) != i && LineDist(P[i], P[i+1], P[h]) <= LineDist(P[i], P[i+1], P[Next(h)])+Eps; h = Next(h));
        for (; Project(P[i], P[i+1], P[l]) < Project(P[i], P[i+1], P[Next(l)]) == (P[i] > P[i+1]); l = Next(l));
        for (; Project(P[i], P[i+1], P[r]) < Project(P[i], P[i+1], P[Next(r)]) == (P[i] < P[i+1]); r = Next(r));
        Solution = min(Solution, LineDist(P[i], P[i+1], P[h])*Distance(Project(P[i], P[i+1], P[l]), Project(P[i], P[i+1], P[r])));
    }
}

void Read() {
    freopen("rubarba.in", "r", stdin);
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i)
        scanf("%lf %lf", &P[i].x, &P[i].y);
    P[N+1] = P[1];
}

void Print() {
    freopen("rubarba.out", "w", stdout);
    printf("%.2lf\n", Solution);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}