Cod sursa(job #2519267)

Utilizator david.teacaDavid Stefan Teaca david.teaca Data 7 ianuarie 2020 14:55:08
Problema Rubarba Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.83 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <iomanip>
 
using namespace std;
 
ifstream fin("rubarba.in");
ofstream fout("rubarba.out");
 
const int NMAX = 1e5;
 
struct Punct
{
    long long x, y;
};
 
struct Dreapta
{
    long double a, b, c;
};
 
int N;
Punct v[NMAX + 5];
vector <Punct> hull;
 
Dreapta dreapta(Punct p1, Punct p2)
{
    Dreapta d1 = {p2.y - p1.y, p1.x - p2.x, p1.y * p2.x - p1.x * p2.y};
    long double aux = sqrt((long double)d1.a * d1.a + d1.b * d1.b);
    long double k = 1 / aux;
    d1.a *= k;
    d1.b *= k;
    d1.c *= k;
    return d1;
}
 
Dreapta perp(Punct a, Dreapta d)
{
    Dreapta d1 = {-d.b, d.a, d.b * a.x - d.a * a.y};
    long double aux = sqrt((long double)d1.a * d1.a + d1.b * d1.b);
    long double k = 1 / aux;
    d1.a *= k;
    d1.b *= k;
    d1.c *= k;
    return d1;
}
 
long double distd(Punct a, Dreapta d)
{
    return (long double)a.x * d.a + a.y * d.b + d.c;
}
 
long long cross_product(Punct P1, Punct P2, Punct P3)
{
    return 1LL * (P2.x - P1.x) * (P3.y - P1.y) -
           1LL * (P2.y - P1.y) * (P3.x - P1.x);
}
 
inline bool cmp(const Punct A, const Punct B)
{
    return cross_product(v[1], A, B) < 0;
}
 
void ReadAndHull()
{
    fin >> N;
 
    int x, y;
    for(int i = 1; i <= N; i++)
    {
        fin >> x >> y;
        v[i] = {x, y};
    }
 
    for(int i = 2; i <= N; i++)
        if((v[i].x == v[1].x && v[i].y < v[1].y) || v[i].x < v[1].x)
            swap(v[1], v[i]);
 
    sort(v + 2, v + N + 1, cmp);
 
    hull.push_back(v[1]);
    for(int i = 2; i <= N; i++)
    {
        while (hull.size() > 1 && cross_product(hull[hull.size() - 2], hull[hull.size() - 1], v[i]) >= 0)
            hull.pop_back();
 
        hull.push_back(v[i]);
    }
}
 
const long double INF = 2000000000;
 
void Solve()
{
    long double ans = 100 * INF;
 
    for(int i = 0; i < hull.size(); i++)
    {
        long double di1, di2, di3;
        di1 = di2 = -INF;
        di3 = INF;
 
        Dreapta d1;
        if(i == hull.size() - 1)
            d1 = dreapta(hull[hull.size() - 1], hull[0]);
        else
            d1 = dreapta(hull[i], hull[i + 1]);
        Dreapta d2 = perp(hull[i], d1);
 
        for (long long j = 0; j < hull.size(); ++j)
        {
            long double dist1 = fabs(distd(hull[j], d1));
            long double dist2 = distd(hull[j], d2);
 
            if (di1 < dist1)
                di1 = dist1;
 
            if (di2 < dist2)
                di2 = dist2;
 
            if (di3 > dist2)
                di3 = dist2;
        }
 
        long double dst = di2 - di3;
        ans = min(ans, dst * di1);
    }
 
    fout << fixed << setprecision(2) << ans << '\n';
}
 
int main()
{
    ReadAndHull();
 
    Solve();
 
    return 0;
}