Cod sursa(job #2678063)

Utilizator trifangrobertRobert Trifan trifangrobert Data 28 noiembrie 2020 02:20:20
Problema Rubarba Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.14 kb
///fereasca sfantu ce-i cu problema asta

#include <iostream>

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

using namespace std;

const int NMAX = 100000;
int N;
vector <pdd> points;

long double det(pdd a, pdd b, pdd c) {
    long double res = 0;
    res += 1LL * a.first * b.second;
    res += 1LL * b.first * c.second;
    res += 1LL * c.first * a.second;
    res -= 1LL * c.first * b.second;
    res -= 1LL * a.first * c.second;
    res -= 1LL * b.first * a.second;
    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;
}

long double Slope(pdd x, pdd y) {
    long double a = x.second - y.second;
    long double b = y.first - x.first;
    return -1.0 * a / b;
}

pdd Projection(long double slopeSeg, long double slopePer, pdd point1, pdd point2) {
    long double m1 = slopeSeg;
    long double n1 = point1.second - slopeSeg * point1.first;
    long double m2 = slopePer;
    long double n2 = point2.second - slopePer * point2.first;
    long double x = 1.0 * (n2 - n1) / (m1 - m2);
    long double y = m1 * x + n1;
    return mp(x, y);
}

long double DistPoints(pdd point1, pdd point2) {
    long double dx = point1.first - point2.first;
    long double dy = point1.second - point2.second;
    return sqrtl(1LL * dx * dx + 1LL * dy * dy);
}

long double Dist(pdd pointLeft, pdd pointRight, pdd point){
    long double distLeft = DistPoints(pointLeft, point);
    long double distRight = DistPoints(pointRight, point);
    long double dist = DistPoints(pointLeft, pointRight);
    if (distLeft + distRight == dist)
        return -1;
    if (distLeft <= distRight)
        return -1;
    return distRight;
}

long double DistPointLine(long double slopeSeg, pdd point1, pdd point2) {
    long double m = slopeSeg;
    long double n = point1.second - slopeSeg * point1.first;
    long double a = -m;
    long double b = 1;
    long double c = -n;
    return 1.0 * abs(a * point2.first + b * point2.second + c) / sqrtl(1LL * a * a + 1LL * b * b);
}

long double DistLines(long double slope, pdd point1, pdd point2) {
    long double n1 = point1.second - slope * point1.first;
    long double n2 = point2.second - slope * point2.first;
    return abs(n1 - n2);
}

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);
    /*for (auto& i : hull)
        cerr << i.first << " " << i.second << "\n";
    cerr << "\n";*/
    N = hull.size();
    int pleft = 1, pright = 1, pmid = 1;
    long double answer = (1LL << 60);
    for (int i = 0; i < N; ++i) {
        long double slopeSeg = Slope(hull[i], hull[(i + 1) % N]);
        long double slopePer = -1.0 / slopeSeg;
        //pdd proj = Projection(slopeSeg, slopePer, hull[i], hull[(i + 2) % N]);
        /*cerr << slopeSeg << " " << slopePer << "\n";
        cerr << proj.first << " " << proj.second << "\n";*/
        while (Dist(hull[i], hull[(i + 1) % N], Projection(slopeSeg, slopePer, hull[i], hull[pright])) <= Dist(hull[i], hull[(i + 1) % N], Projection(slopeSeg, slopePer, hull[i], hull[(pright + 1) % N])))
            pright = (pright + 1) % N;
        while (Dist (hull[(i + 1) % N], hull[i], Projection(slopeSeg, slopePer, hull[i], hull[pleft])) <= Dist(hull[(i + 1) % N], hull[i], Projection(slopeSeg, slopePer, hull[i], hull[(pleft + 1) % N])))
            pleft = (pleft + 1) % N;
        while (DistPointLine(slopeSeg, hull[i], hull[pmid]) <= DistPointLine(slopeSeg, hull[i], hull[(pmid + 1) % N]))
            pmid = (pmid + 1) % N;
        long double x = DistPoints(Projection(slopeSeg, slopePer, hull[i], hull[pright]), Projection(slopeSeg, slopePer, hull[i], hull[pleft]));
        long double y = DistPointLine(slopeSeg, hull[i], hull[pmid]);
        answer = min(answer, x * y);
    }
    fout << setprecision(2) << fixed;
    fout << answer << "\n";
    fin.close();
    fout.close();
    return 0;
}