Pagini recente » Cod sursa (job #1433599) | Cod sursa (job #3126197) | Cod sursa (job #1062787) | Cod sursa (job #1503385) | Cod sursa (job #2402090)
#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;
}