Cod sursa(job #987982)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 21 august 2013 18:40:03
Problema Rubarba Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.73 kb
#include <cmath>
#include <cstring>

#include <fstream>
#include <iomanip>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<double, double> Point;

const double oo = 1e13;
const double Eps = 1e-12;

vector<Point> P;
int N;
double Solution;

inline double Det(const Point &A, const Point &B, const Point &C) {
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

vector<Point> ConvexHull(vector<Point> points) {
    int n = static_cast<int>(points.size());
    vector<int> stack = vector<int>(n + 2, 0);
    int origin = 0;
    for (int i = 1; i < n; ++i)
        if (points[i] < points[origin])
            origin = i;
    swap(points[0], points[origin]);
    sort(points.begin() + 1, points.end(), [&points](const Point &A, const Point &B) -> bool {
         return atan2(A.y - points[0].y, A.x - points[0].x) < atan2(B.y - points[0].y, B.x - points[0].x);
    });
    stack[++stack[0]] = 0;
    stack[++stack[0]] = 1;
    for (int i = 2; i < n; ++i) {
        while (stack[0] > 1 && Det(points[stack[stack[0] - 1]], points[stack[stack[0]]], points[i]) < Eps)
            --stack[0];
        stack[++stack[0]] = i;
    }
    vector<Point> hull;
    for (int i = 1; i <= stack[0]; ++i)
        hull.push_back(points[stack[i]]);
    return hull;
}

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(const Point &P1, const Point &P2, const Point &Q) {
    if (abs(P1.x - P2.x) < Eps)
        return Point(P1.x, Q.y);
    if (abs(P1.y - P2.y) < Eps)
        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(const Point &P1, const Point &P2) {
    return sqrt((P1.x - P2.x) * (P1.x - P2.x) + (P1.y - P2.y) * (P1.y - P2.y));
}

inline double LineDistance(const Point &P1, const Point &P2, const Point &Q) {
    if (abs(P1.x - P2.x) < Eps)
        return abs(Q.x - P1.x);
    if (abs(P1.y - P2.y) < Eps)
        return abs(Q.y - P1.y);
    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(const int index) {
    return (index + 1) % N;
}

void Solve() {
    P = ConvexHull(P);
    N = int(P.size());
    Solution = oo;
    int l = 0, r = 0;
    for (int i = 1; i < N; ++i) {
        if (Project(P[0], P[1], P[l]) > Project(P[0], P[1], P[i]))
            l = i;
        if (Project(P[0], P[1], P[r]) < Project(P[0], P[1], P[i]))
            r = i;
    }
    for (int i = 0, h = 2; i < N; ++i) {
        while (Next(h) != i && LineDistance(P[i], P[i + 1], P[h]) <= LineDistance(P[i], P[i + 1], P[Next(h)]) + Eps)
            h = Next(h);
        while ((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);
        while ((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, LineDistance(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);
    ifstream cin("rubarba.in");
    cin >> N;
    P.resize(N);
    for (int i = 0; i < N; ++i)
        cin >> P[i].x >> P[i].y;
    cin.close();
}

void Print() {
    ofstream cout("rubarba.out");
    cout << fixed << setprecision(2) << Solution << "\n";
    cout.close();
}

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