Cod sursa(job #2402090)

Utilizator MoldovanAndrei1Moldovan Andrei MoldovanAndrei1 Data 10 aprilie 2019 12:33:07
Problema Rubarba Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps=1.e-14;
struct dd
{
    double x,y;
}ll;
double cp(dd a,dd b,dd c)
{
    return (b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
}
int ccw(dd a,dd b,dd c)
{
    double r=cp(a,b,c);
    if(r<-eps)return -1;
    return 1;
}
double ds(dd a,dd b)
{
  return sqrt((double)((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}
bool cmp(dd a,dd b)
{
    int s=ccw(ll,a,b);
    if(s>0)return 1;
    return 0;
}
dd a[120005];
dd v[120005];
int main()
{
    freopen("rubarba.in","r",stdin);
    freopen("rubarba.out","w",stdout);
    int n , i,j;
    scanf("%d",&n);
scanf("%lf%lf",&ll.x,&ll.y);
    a[0]=ll;
    for(i=1;i<n;i++)
        {
            scanf("%lf%lf",&a[i].x,&a[i].y);
            if(fabs(ll.y-a[i].y)<eps)
            {
                if(ll.x-a[i].x>=eps)
                    {
                        ll=a[i];
                        a[i]=a[0];
                        a[0]=ll;
                    }
                    continue;
            }
            if(ll.y-a[i].y>=eps)
                {
                                            ll=a[i];
                        a[i]=a[0];
                        a[0]=ll;
                }
        }
        sort(a+1,a+n,cmp);
        int cnt=2;
        v[1]=ll;
        v[2]=a[1];
        for(i=2;i<n;i++)
        {
            dd t1=v[cnt-1],t2=v[cnt];
            while(ccw(t1,t2,a[i])<0)
            {
                --cnt;
                t1=v[cnt-1],t2=v[cnt];
            }
            cnt++;
            v[cnt]=a[i];
        }
        double arie_min=9999999999999;
      for(i=1;i<cnt;i++)
      {
        for(j=i+1;j<=cnt;j++)
        {
          double a1=v[j].y-v[i].y,b1=v[i].x-v[j].x,c1=v[j].x*v[i].y-v[i].x*v[j].y;
          double d1=0,d2=0;
          double lat_max=sqrt(a1*a1+b1*b1);
          double l3=0;
          for(int t=1;t<=cnt;t++)
          {
            if(t==i)continue;if(t==j)continue;
            double dist1=a1*v[t].x+b1*v[t].y+c1;
            if(dist1<=-1*eps)dist1*=-1;
            dist1/=sqrt(a1*a1+b1*b1);
            if(ccw(v[i],v[j],v[t])>0&&d1<dist1)d1=dist1;
            if(ccw(v[i],v[j],v[t])<0&&d2<dist1)d2=dist1;
            double l1=ds(v[i],v[t]),l2=ds(v[j],v[t]);
            double p1=sqrt((l1*l1)-dist1*dist1),p2=sqrt((l2*l2)-dist1*dist1);
            if(ds(v[i],v[j])-p1-p2>=-1*eps)continue;
            if(p1<p2)
            {
              if(l3<p1)l3=p1;
            }
            if(p1>p2)
              if(lat_max<p1)lat_max=p1;
          }
          double r1=d1+d2;
          r1*=lat_max+l3;
          if(r1<arie_min)arie_min=r1;
        }
      }
      printf("%.2lf\n",arie_min);
    return 0;
}