Cod sursa(job #2122988)

Utilizator edynator34Nechitoaia George-Edward edynator34 Data 5 februarie 2018 18:11:17
Problema Rubarba Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
#include <algorithm>
using namespace std;
ifstream in("rubarba.in");
ofstream out("rubarba.out");
int n,j,i,k;
double sol=99999999999;
struct punct{double x; double y;} p[100005];
punct s[100005];

double determinant (punct a, punct b,punct c){
    return ((a.x*b.y)+(b.x*c.y)+(a.y*c.x)-(b.y*c.x)-(a.x*c.y)-(b.x*a.y));
}
bool comp(punct i, punct j){
    double d=determinant(p[1],i,j);
    if(d>0) return true;
    return false;

}

double distanta(punct a,punct b)
{
    return sqrt(((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}




void solve(punct a,punct b)
{
    if(!(a.x<=b.x))
        swap(a,b);
    double m,b1,b2,dist=0;
    m=(1.0*b.y-a.y)/(b.x-a.x);
    b1=1.0*(1.0*a.y*(b.x-a.x)-1.0*a.x*(b.y-a.y))/(b.x-a.x);
    punct p,l,c,aux;
    l.x=a.x;
    l.y=a.y;
    c.x=b.x;
    c.y=b.y;
     for(int i=1;i<=k;i++)
        if((s[i].x!=a.x||s[i].y!=a.y)&&(s[i].x!=b.x||s[i].y!=b.y))
        {
            if(b.x==a.x)
            {
                p.x=a.x;
                p.y=s[i].y;
            }
            else
                if(b.y==a.y)
                {
                    p.x=s[i].x;
                    p.y=a.y;
                }
                else
                {
                    b2=s[i].y+1.0*s[i].x/m;
                    p.x=m*(1.0*b2-b1)/(m*m+1);
                    p.y=m*p.x+b1;
                }
            aux.x=s[i].x;
            aux.y=s[i].y;
            dist=max(dist,distanta(aux,p));
            if(b.x!=a.x)
            {
                if(p.x>=c.x)
                    c=p;
                if(p.x<=l.x)
                    l=p;
            }
            else
            {
                c.y=max(c.y,p.y);
                l.y=min(l.y,p.y);
            }
        }
    sol=min(sol,dist*distanta(l,c));
}



int main()
{
    in>>n;
    in>>p[1].x>>p[1].y;
    j=1;
    for(i=2;i<=n;++i)
    {
        in>>p[i].x>>p[i].y;
        if(p[i].x<p[j].x || (p[i].x==p[i].x && p[i].y<p[i].y)) j=i;
    }
    swap(p[1],p[j]);
    sort(p+2,p+n+1,comp);
    s[1]=p[1];s[2]=p[2];k=2;
    for(i=3;i<=n;++i){
    while(k>1 && determinant(s[k-1],s[k],p[i])<0)--k;
    k++;s[k]=p[i];
        }
    /*out<<k<<'\n';
    out<<fixed;
    for(i=1;i<=k;++i) out<<setprecision(6)<<s[i].x<<' '<<setprecision(6)<<s[i].y<<'\n';
        */
    for(i=1;i<=k;++i){
        solve(s[i],s[i+1]);
    }

    out<<fixed<<setprecision(2)<<sol;
    return 0;
}