Cod sursa(job #2857356)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 25 februarie 2022 14:23:25
Problema Rubarba Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.44 kb

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

#define cx first
#define cy second
#define pdd pair <double, double>

ifstream fin("rubarba.in");
ofstream fout("rubarba.out");

const int maxN = 100005;
const double eps = 1e-12;
int n, st, dr, cap;
pdd pct[maxN];
double ans;
vector <pdd> inf, sus, jos;

double arie(pdd a, pdd b, pdd c)
{
    /// ax ay 1 )
    /// bx by 1  ) => d = ax * by + ay * cx + bx * cy - by * cx - ay * bx - ax * cy
    /// cx cy 1 )
    return a.cx * b.cy + a.cy * c.cx + b.cx * c.cy - b.cy * c.cx - a.cy * b.cx - a.cx * c.cy;
}

double dist(pdd a, pdd b)
{
    return sqrt((a.cx - b.cx) * (a.cx - b.cx) + (a.cy - b.cy) * (a.cy - b.cy));
}

double pct_dr(pdd a, pdd b, pdd x)
{
    return arie(a, x, b) / dist(a, b);
}

pdd pp(pdd a, pdd b, pdd x)
{
    pdd punct;
    punct.cx = x.cx - a.cy + b.cy;
    punct.cy = x.cy + a.cx - b.cx;
    return punct;
}

void infasuratoare()
{
    sort(pct + 1, pct + n + 1);
    sus.push_back(pct[1]);
    jos.push_back(pct[1]);
    for(int i = 2; i <= n; i++)
    {
        while(sus.size() >= 2 && arie(sus[sus.size() - 2], sus[sus.size() - 1], pct[i]) >= -eps)
            sus.pop_back();
        sus.push_back(pct[i]);
        while(jos.size() >= 2 && arie(jos[jos.size() - 2], jos[jos.size() - 1], pct[i]) <= eps)
            jos.pop_back();
        jos.push_back(pct[i]);
    }

    for(pdd ind : sus)
        inf.push_back(ind);
    for(int i = jos.size() - 1; i >= 0; i--)
    {
        pdd ind = jos[i];
        if(ind != pct[1] && ind != pct[n])
            inf.push_back(ind);
    }
    n = inf.size() - 1;
    //fout << n << '\n';
    //for(pdd ind : inf)
    //    fout << ind.cx << ' ' << ind.cy << '\n';
}

int next(int x)
{
    if(x == n)
        return 0;
    else
        return x + 1;
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> pct[i].cx >> pct[i].cy;
    infasuratoare();
    st = 1, dr = 1, cap = 1;
    pdd T = pp(inf[0], inf[1], inf[0]);
    for(int i = 2; i <= n; i++)
    {
        if(pct_dr(inf[0], inf[1], inf[i]) - pct_dr(inf[0], inf[1], inf[cap]) >= -eps)
            cap = i;
        if(pct_dr(inf[0], T, inf[i]) - pct_dr(inf[0], T, inf[st]) >= eps)
            st = i;
        if(pct_dr(inf[0], T, inf[i]) - pct_dr(inf[0], T, inf[dr]) <= -eps)
            dr = i;
    }
    ans = abs(pct_dr(inf[0], inf[1], inf[cap]) * pct_dr(inf[dr], pp(inf[0], inf[1], inf[dr]), inf[st]));
    for(int i = 1; i <= n; i++)
    {
        int ind = next(i);
        T = pp(inf[i], inf[ind], inf[i]);
        while(pct_dr(inf[i], inf[ind], inf[next(cap)]) - pct_dr(inf[i], inf[ind], inf[cap]) >= -eps)
            cap = next(cap);
        while(pct_dr(inf[i], T, inf[next(st)]) - pct_dr(inf[i], T, inf[st]) >= eps)
            st = next(st);
        while(pct_dr(inf[i], T, inf[next(dr)]) - pct_dr(inf[i], T, inf[dr]) <= -eps)
            dr = next(dr);
        double arie_dr = abs(pct_dr(inf[i], inf[ind], inf[cap]) * pct_dr(inf[dr], pp(inf[i], inf[ind], inf[dr]), inf[st]));
        //fout << i << ' ' << ind << ' ' << st << ' ' << dr << ' ' << cap << ' ' << pct_dr(inf[i], inf[ind], inf[cap]) << ' ' << pct_dr(inf[dr], pp(inf[i], inf[ind], inf[dr]), inf[st]) << "    " << arie_dr << '\n';
        ans = min(ans, arie_dr);
    }
    fout << fixed << setprecision(2) << ans << '\n';
    return 0;
}