Cod sursa(job #2402133)

Utilizator MoldovanAndrei1Moldovan Andrei MoldovanAndrei1 Data 10 aprilie 2019 13:04:42
Problema Rubarba Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.93 kb
#include <cstdio>
#include <algorithm>
#include<cmath>
using namespace std;
const double eps=1.e-4;
struct dd
{
    double x,y;
};
dd a[220005];
dd ll;
dd st[2005];
double dist(dd a1,dd b1)
{
    return (a1.x-b1.x)*(a1.x-b1.x)+(a1.y-b1.y)*(a1.y-b1.y);
}
double cp(dd a1,dd b,dd c)
{
    return(b.x-a1.x)*(c.y-b.y)-(b.y-a1.y)*(c.x-b.x);
}
int ccw(dd m,dd n ,dd q)
{
    double cp1=cp(m,n,q);
    if(cp1==0)return 0;
    if(cp1>0)return 1;
    if(cp1<0)return -1;
}
bool cmp(dd m,dd n)
{
    double cp1=cp(ll,m,n);
    if(cp1==0)return dist(ll,m)<dist(ll,n);
    if(cp1>0)return 1;
    return 0;
}
double ds(dd m,dd n)
{
  return sqrt((m.x-n.x)*(m.x-n.x)+(m.y-n.y)*(m.y-n.y));
}
int main()
{
    freopen("rubarba.in","r",stdin);
    freopen("rubarba.out","w",stdout);
    int n,i;
    ll.x=ll.y=10000001;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lf%lf",&a[i].x,&a[i].y);
        if(a[i].y==ll.y&&a[i].x<ll.x)ll=a[i];
        if(a[i].y<ll.y)ll=a[i];
    }
    sort(a+1,a+n+1,cmp);
    int cnt=0;
    st[++cnt]=a[1];
    st[++cnt]=a[2];
    for(i=3;i<=n;i++)
    {
        if(ccw(st[cnt-1],st[cnt],a[i])>=0)
        {
            st[++cnt]=a[i];
            continue;
        }
        int j=i;
        while(ccw(ll,st[cnt],a[j])==0&&dist(ll,st[cnt])<dist(ll,a[j]))j++;
        if(j!=i)
        {
            int st1=i-1,dr1=j-1;
            dd aux;
            while(st1<dr1)
            {
                aux=a[st1];
                a[st1]=a[dr1];
                a[dr1]=aux;
                st1++;
                dr1--;
            }
            cnt--;
            i-=2;
            continue;
        }
        while(ccw(st[cnt-1],st[cnt],a[i])<0)cnt--;
        st[++cnt]=a[i];
    }

        double arie_min=9999999999999;
        int j;
      for(i=1;i<cnt;++i)
      {
        for(j=i+1;j<=cnt;++j)
        {
          double a1=st[j].y-st[i].y,b1=st[i].x-st[j].x,c1=st[j].x*st[i].y-st[i].x*st[j].y;
          double d1=0,d2=0;
          double lat_max=sqrt(a1*a1+b1*b1);
          double l3=0;
          double r1=ds(st[i],st[j]);
          for(int t=1;t<=cnt;t++)
          {
            if(t==i)continue;if(t==j)continue;
            double dist1=a1*st[t].x+b1*st[t].y+c1;
            if(dist1<=-1*eps)dist1*=-1;
            dist1/=sqrt(a1*a1+b1*b1);
            if(ccw(st[i],st[j],st[t])>0&&d1<dist1)d1=dist1;
            if(ccw(st[i],st[j],st[t])<0&&d2<dist1)d2=dist1;
            double l1=ds(st[i],st[t]),l2=ds(st[j],st[t]);
            double p1=sqrt((l1*l1)-dist1*dist1),p2=sqrt((l2*l2)-dist1*dist1);
            if(r1-p1-p2>=-1*eps)continue;
            if(p1<p2)
            {
              if(l3<p1)l3=p1;
            }
            if(p1>p2)
              if(lat_max<p1)lat_max=p1;
          }
          r1=d1+d2;
          r1*=lat_max+l3;
          if(r1<arie_min)arie_min=r1;
        }
      }
      printf("%.2lf\n",arie_min);
    return 0;
}