Cod sursa(job #2682960)

Utilizator trifangrobertRobert Trifan trifangrobert Data 10 decembrie 2020 00:14:15
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.75 kb
///fereasca sfantu ce-i cu problema asta

#include <iostream>

#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <cmath>
#define pdd pair <long double, long double>
#define mp make_pair
#define all(x) x.begin(), x.end()

using namespace std;

const long long INF = (1LL << 50);
int N;
vector <pdd> points;

struct Line {
    long double a, b, c;
    Line() {
        this->a = this->b = this->c = 0;
    }
    Line(long double a, long double b, long double c) {
        this->a = a;
        this->b = b;
        this->c = c;
    }
    Line(pdd a, pdd b) {
        this->a = a.second - b.second;
        this->b = b.first - a.first;
        this->c = a.first * b.second - a.second * b.first;
    }
    Line Perpendicular(pdd point) {
        return Line(-this->b, this->a, (long double)this->b * point.first - (long double)this->a * point.second);
    }
};

long double det(pdd a, pdd b, pdd c) {
    long double res = 0;
    res += a.first * b.second;
    res += b.first * c.second;
    res += c.first * a.second;
    res -= b.second * c.first;
    res -= c.second * a.first;
    res -= a.second * b.first;
    return res;
}

vector <pdd> ConvexHull(vector <pdd> points) {
    vector <pdd> stk;
    stk.push_back(points[0]);
    for (int i = 1; i < points.size(); ++i) {
        while (stk.size() >= 2 && det(stk[stk.size() - 2], stk.back(), points[i]) <= 0)
            stk.pop_back();
        stk.push_back(points[i]);
    }
    return stk;
}

int nxt(int i) {
    return (i + 1) % N;
}

long double DistPointLine(Line line, pdd point) {
    return (long double)(line.a * point.first + line.b * point.second + line.c) / sqrtl(line.a * line.a + line.b * line.b);
}

int main() {
    ifstream fin("rubarba.in");
    ofstream fout("rubarba.out");
    fin >> N;
    points = vector <pdd>(N);
    for (int i = 0; i < N; ++i)
        fin >> points[i].first >> points[i].second;
    sort(all(points));
    vector <pdd> pointsUnder, pointsOver;
    pointsUnder.push_back(points[0]);
    pointsOver.push_back(points[0]);
    for (int i = 1; i < N - 1; ++i) {
        if (det(points[0], points[i], points.back()) >= 0)
            pointsUnder.push_back(points[i]);
        else
            pointsOver.push_back(points[i]);
    }
    pointsUnder.push_back(points.back());
    pointsOver.push_back(points.back());
    reverse(all(pointsOver));
    vector <pdd> hullUnder = ConvexHull(pointsUnder);
    vector <pdd> hullOver = ConvexHull(pointsOver);
    hullUnder.pop_back();
    hullOver.pop_back();
    vector <pdd> hull;
    for (auto& i : hullUnder)
        hull.push_back(i);
    for (auto& i : hullOver)
        hull.push_back(i);
    N = hull.size();
    if (N <= 2) {
        fout << "0.00\n";
        return 0;
    }
    int indMid, indLeft, indRight;
    long double distMid = -INF, distLeft = INF, distRight = -INF;
    Line dPar = Line(hull[0], hull[1]);
    Line dPer = dPar.Perpendicular(hull[0]);
    for (int i = 0; i < N; ++i) {
        long double distPar = fabs(DistPointLine(dPar, hull[i]));
        long double distPer = DistPointLine(dPer, hull[i]);
        if (distPar > distMid) {
            distMid = distPar;
            indMid = i;
        }
        if (distPer > distRight) {
            distRight = distPer;
            indRight = i;
        }
        if (distPer < distLeft) {
            distLeft = distPer;
            indLeft = i;
        }
    }
    long double answer = distMid * (distRight - distLeft);
    for (int i = 1; i < N; ++i) {
        dPar = Line(hull[i], hull[nxt(i)]);
        dPer = dPar.Perpendicular(hull[i]);
        distMid = fabs(DistPointLine(dPar, hull[indMid]));;
        distLeft = DistPointLine(dPer, hull[indLeft]);
        distRight = DistPointLine(dPer, hull[indRight]);
        long double nextDist = fabs(DistPointLine(dPar, hull[nxt(indMid)]));
        while (nextDist >= distMid) {
            distMid = nextDist;
            indMid = nxt(indMid);
            nextDist = fabs(DistPointLine(dPar, hull[nxt(indMid)]));
        }
        nextDist = DistPointLine(dPer, hull[nxt(indRight)]);
        while (nextDist >= distRight) {
            distRight = nextDist;
            indRight = nxt(indRight);
            nextDist = DistPointLine(dPer, hull[nxt(indRight)]);
        }
        nextDist = DistPointLine(dPer, hull[nxt(indLeft)]);
        while (nextDist <= distLeft) {
            distLeft = nextDist;
            indLeft = nxt(indLeft);
            nextDist = DistPointLine(dPer, hull[nxt(indLeft)]);
        }
        answer = min(answer, distMid * (distRight - distLeft));
    }
    fout << setprecision(2) << fixed;
    fout << answer << "\n";
    fin.close();
    fout.close();
    return 0;
}