Cod sursa(job #1779746)

Utilizator ValentinSavoiuFMI Savoiu Valentin-Marian ValentinSavoiu Data 15 octombrie 2016 16:24:13
Problema Rubarba Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <cmath>
#define x first
#define y second
#define MAX_N  120005
#define inf 1e9
using namespace std;
typedef pair<float, float> Point;
const double EPS = 1e-12;//10^(-12)
ifstream f("rubarba.in");
ofstream g("rubarba.out");
int n,p,i,xmin,xmax,ymin,ymax,j;
float arie,ariemin,panta,panta2,c,b,cmin,cmax,bmin,bmax;
Point v[MAX_N],m,m2,m3,m4;
bool vis[MAX_N];
int st[MAX_N], head;
float prod(Point O, Point A, Point B) {
    return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}

int main()
{
    f>> n;
    for ( i = 1; i <= n; ++i)
        f >> v[i].x >> v[i].y;
    sort(v + 1, v + n + 1);

    st[1] = 1; st[2] = 2; head = 2;
    vis[2] = true;

    for (i = 1, p = 1; i > 0; i +=p )
    {
        if(i==n) p=-1;
        if (vis[i]) continue;
        while (head >= 2 && prod(v[st[head - 1]], v[st[head]], v[i]) < EPS)
            vis[st[head--]] = false;
        st[++head] = i;
        vis[i] = true;
    }
    xmin=ymin=10000000; xmax=ymax=-1;
    for(i=1;i<head;i++)
    {
        if(v[st[i]].x<xmin) xmin=v[st[i]].x;
        if(v[st[i]].x>xmax) xmax=v[st[i]].x;
        if(v[st[i]].y<ymin) ymin=v[st[i]].y;
        if(v[st[i]].y>ymax) ymax=v[st[i]].y;
    }
    ariemin=(xmax-xmin)*(ymax-ymin);
    ariemin=ariemin*ariemin;
    for(i=1;i<head;i++)
    {
        if(v[st[i]].x!=v[st[i]+1].x)
        {
            panta=(v[st[i+1]].y-v[st[i]].y)/(v[st[i+1]].x-v[st[i]].x);
            panta2=-1/panta;
            cmin=bmin=inf; cmax=bmax=-inf;
            for(j=1;j<head;j++)
            {
                c=(v[st[j]].y-panta*v[st[j]].x);
                b=(v[st[j]].y-panta2*v[st[j]].x);
                if(c<cmin) cmin=c;
                if(c>cmax) cmax=c;
                if(b<bmin) bmin=b;
                if(b>bmax) bmax=b;
            }
            arie=(cmax-cmin)/sqrt(1+panta*panta)*((bmax-bmin)/sqrt(1+panta2*panta2));
            if(arie<ariemin) ariemin=arie;
        }
    }
    g<<fixed<<setprecision(2)<<ariemin<<'\n';
    return 0;
}