Cod sursa(job #1491749)

Utilizator lflorin29Florin Laiu lflorin29 Data 26 septembrie 2015 00:12:01
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.02 kb
#include <bits/stdc++.h>

using namespace std;

const int kPoints = (int)1e5 + 5;
const long double kInfinite = numeric_limits <long double>:: max();
const long double NUL = 0;

int n;
int szhul;
pair <double, double> hul[kPoints];
bool amFol[kPoints];
pair <double, double> points[kPoints];

void read() {
    ifstream fin ("rubarba.in");
    fin >> n;

    for (int i = 1; i <= n; ++i)
        fin >> points[i].first >> points[i].second;
}

inline double CrossProduct (const pair <double, double> &O, const pair <double, double> &a, const pair <double, double> &b) {
    return  (a.first - O.first)  * (b.second - O.second) -  (b.first - O.first) * (a.second - O.second);
}

inline double DotProduct (const pair <double, double> &O, const pair <double, double> &a, const pair <double, double> &b) {
    return  (a.first - O.first) *  (b.first - O.first) + (a.second - O.second) * (b.second - O.second);
}

void createHull() {
    stack < pair <double, double> > pp;
    for (int i = 1; i <= n; ++i)
        if (points[i] < points[1])
          swap(points[1], points[i]); // min point

    auto lambda = [&] (const pair <double, double> &a, const pair <double , double> &b) ->bool {
        return CrossProduct(points[1], a, b) > 0;
    };
    sort(points + 2, points + n + 1, lambda);

    pp.push(points[1]);
    pp.push(points[2]);

    for (int i = 3; i <= n; ++i) {
        while (pp.size() >= 2) {
             pair <double, double> curent = pp.top();
             pp.pop();
             pair <double, double> inainte = pp.top();

             if (CrossProduct(inainte, curent, points[i]) <= 0)
                continue;
              pp.push(curent);
              break;
        }
        pp.push(points[i]);
    }

    for (; not pp.empty(); pp.pop())
       hul[++szhul] = pp.top();

    n = szhul;

    reverse(hul + 1, hul + szhul + 1);

}

inline int next (int const& x) {
    if (x == n)
        return 1 ;
    return 1 + x ; // v[i + 1]
}

inline pair <double, double> Rotate(int const& A) { // translate ..
    int Son = next(A);
    int d1 = hul[Son].first - hul[A].first, d2 = hul[Son].second - hul[A].second;
    return {d1, d2};
}

// CrosProd(i,j) = |i| * |j| * sin(i,j)
// DotProd(i, j) = |i| * j| * cos(i, j)

//daca crosprod(i,j) > 0  unghiul x dintre i si j e intre 0 si 180
// Daca DotProd > 0 , Cos(x = unghiul) e < 90

double DistantaDr (const pair <double, double> &a, const pair <double, double> &b, const double& med) { //med este panta
    return fabs((a.second - med * a.first) - (b.second - med * b.first)) / sqrt(med * med + 1.0);
}

void Solve() {
    ofstream fout ("rubarba.out");
    createHull();
    long double ret = kInfinite; // Min area :)
    pair <double, double> const&  O = {0, 0};
    int j = 1 , k , m;

    for (int i = 1; i <= n; ++i) {
       double cine1, cine2;
       while (DotProduct(O, Rotate(i), Rotate(j)) > NUL)
            j = next(j);

        if (i == 1)
            k = j;

       while (CrossProduct(O, Rotate(i), Rotate(k)) > NUL)
            k = next(k);

        if (i == 1)
            m = k;

       while (DotProduct(O, Rotate(i), Rotate(m)) < NUL)
            m = next(m);

        bool caz1 = hul[i].first == hul[next(i)].first,
        caz2 = hul[i].second == hul[next(i)].second;

        if (caz1)
            cine1 = fabs(hul[k].first - hul[i].first), cine2 = fabs(hul[m].second - hul[j].second);

        else if (caz2)
            cine1 = fabs(hul[k].second - hul[i].second), cine2 = fabs(hul[m].first - hul[j].first);

        else {
            double panta = (hul[next(i)].second - hul[i].second) / (hul[next(i)].first - hul[i].first);
            // panta(x1,y1,x2,y2)=(y1-y2)/(x1-x2)
            cine1 = DistantaDr(hul[i], hul[k], panta);
            cine2 = DistantaDr(hul[j], hul[m], -1.0 / panta);

        }

        long double incerc = cine1 * cine2;
        ret = min(ret, incerc);
    }
    fout << fixed << setprecision(2) << ret;
}

int main() {
    read();
    Solve();
}