Pagini recente » Cod sursa (job #2173900) | Cod sursa (job #2574853) | Cod sursa (job #2615065) | Cod sursa (job #1452131) | Cod sursa (job #372633)
Cod sursa(job #372633)
#include<fstream.h>
#include<iomanip.h>
#include<math.h>
double x[100000],y[10000],p[10000];
long a[100000],sol[100000];
long ls(long k)
{
return (k<<1);
}
long rs(long k)
{
return ((k<<1)+1);
}
long f(long k)
{
return (k>>1);
}
void ex(long x, long y)
{
long aux;
aux=a[x];
a[x]=a[y];
a[y]=aux;
}
void sift(long n, long k)
{
long son;
do
{
son=0;
if(ls(k)<=n)
{
son=ls(k);
if(rs(k)<=n&&p[a[rs(k)]]>p[a[son]])son=rs(k);
if(p[a[son]]<=p[a[k]])son=0;
}
if(son)
{
ex(k,son);
k=son;
}
}
while(son);
}
void bh(long n)
{
long i;
for(i=(n>>1);i;i--)sift(n,i);
}
void batman(int n)
{
long i;
bh(n);
for(i=n;i>1;i--)
{
ex(1,i);
sift(i-1,1);
}
}
int det(int q, int w, int e)
{
if(x[q]*y[w]+x[w]*y[e]+x[e]*y[q]>x[w]*y[q]+x[e]*y[w]+x[q]*y[e])return 1;
else return 0;
}
int main()
{
long min,max,k,n,j,i,t,b[100000],st,dr,up,down,semn;
double numa,numi,d,dmax,s,smax,xx[100000],tg,cos,sin,l,ddr,sst,tg2;
ifstream f("rubarba.in");
ofstream g("rubarba.out");
f>>n>>x[1]>>y[1];
min=1;
t=0;
for(i=2;i<=n;i++)
{
f>>x[i]>>y[i];
if(x[i]<x[min]||x[i]==x[min]&&y[i]<y[min])min=i;
}
k=0;
for(i=1;i<=n;i++)
if(x[min]==x[i])b[++k]=i;
else
{
p[i]=(y[i]-y[min])/(x[i]-x[min]);
a[++t]=i;
}
max=b[1];
for(i=2;i<=k;i++)
if(y[b[i]]>max)max=b[i];
batman(t);
sol[1]=min;
sol[2]=a[1];
i=2;j=2;
while(j<=t)
{
while(!det(sol[i-1],sol[i],a[j]))i--;
sol[++i]=a[j++];
}
if(max&&max!=min)
sol[++i]=max;
smax=1000000;
for(j=1;j<=i-1;j++)
{
if(x[sol[j]]==x[sol[j+1]])
{
if(y[sol[j]]>y[sol[j+1]])
{
up=j;
down=j+1;
}
else
{
up=j+1;
down=j;
}
for(k=1;k<=i;k++)
if(k!=j&&k!=j+1)
{
if(y[sol[k]]<down)down=k;
if(y[sol[k]]>up)up=k;
}
l=(x[sol[up]]-x[sol[down]])*(x[sol[up]]-x[sol[down]])+(y[sol[up]]-y[sol[down]])*(y[sol[up]]-y[sol[down]]);
l=sqrt(l);
}
else
{
tg=(y[sol[j+1]]-y[sol[j]])/(x[sol[j+1]]-x[sol[j]]);
if(tg>0)semn=1;
else semn=0;
cos=tg*tg+1;
cos=1/cos;
sin=1-cos;
sin=sqrt(sin);
cos=sqrt(cos);
if(!semn)cos=-cos;
for(k=1;k<=i;k++)
xx[sol[k]]=x[sol[k]]*cos+y[sol[k]]*sin;
sst=1000001;
ddr=-1000001;
for(k=1;k<=i;k++)
if(k!=j&&k!=j+1)
{
if(xx[sol[k]]<sst)
{
st=k;
sst=xx[sol[st]];
}
if(xx[sol[k]]>ddr)
{
dr=k;
ddr=xx[sol[dr]];
}
}
l=(x[sol[dr]]-x[sol[st]])*(x[sol[dr]]-x[sol[st]])+(y[sol[dr]]-y[sol[st]])*(y[sol[dr]]-y[sol[st]]);
l=sqrt(l);
tg2=(y[sol[st]]-y[sol[dr]])/(x[sol[st]]-x[sol[dr]]);
tg=(tg2-tg)/(1+tg*tg2);
cos=tg*tg+1;
cos=1/cos;
cos=sqrt(cos);
l*=cos;
}
dmax=0;
for(k=1;k<=i;k++)
if(k!=j&&k!=j+1)
{
numa=(x[sol[j+1]]-x[sol[j]])*(y[sol[j]]-y[sol[k]])-(x[sol[j]]-x[sol[k]])*(y[sol[j+1]]-y[sol[j]]);
numi=(x[sol[j+1]]-x[sol[j]])*(x[sol[j+1]]-x[sol[j]])+(y[sol[j+1]]-y[sol[j]])*(y[sol[j+1]]-y[sol[j]]);
if(numa<0)numa=-numa;
numi=sqrt(numi);
d=numa/numi;
if(d>dmax)dmax=d;
}
s=dmax*l;
if(s<smax)smax=s;
}
if(x[sol[i]]==x[sol[1]])
{
if(y[sol[i]]>y[sol[1]])
{
up=i;
down=1;
}
else
{
up=1;
down=i;
}
for(k=1;k<=i;k++)
if(k!=i&&k!=1)
{
if(y[sol[k]]<down)down=k;
if(y[sol[k]]>up)up=k;
}
l=(x[sol[up]]-x[sol[down]])*(x[sol[up]]-x[sol[down]])+(y[sol[up]]-y[sol[down]])*(y[sol[up]]-y[sol[down]]);
l=sqrt(l);
}
else
{
tg=(y[sol[1]]-y[sol[i]])/(x[sol[1]]-x[sol[i]]);
if(tg>0)semn=1;
else semn=0;
cos=tg*tg+1;
cos=1/cos;
sin=1-cos;
sin=sqrt(sin);
cos=sqrt(cos);
if(!semn)cos=-cos;
for(k=1;k<=i;k++)
xx[sol[k]]=x[sol[k]]*cos+y[sol[k]]*sin;
sst=1000001;
ddr=-1000001;
for(k=1;k<=i;k++)
if(k!=i&&k!=1)
{
if(xx[sol[k]]<sst)
{
st=k;
sst=xx[sol[st]];
}
if(xx[sol[k]]>ddr)
{
dr=k;
ddr=xx[sol[dr]];
}
}
l=(x[sol[dr]]-x[sol[st]])*(x[sol[dr]]-x[sol[st]])+(y[sol[dr]]-y[sol[st]])*(y[sol[dr]]-y[sol[st]]);
l=sqrt(l);
tg2=(y[sol[st]]-y[sol[dr]])/(x[sol[st]]-x[sol[dr]]);
tg=(tg2-tg)/(1+tg*tg2);
cos=tg*tg+1;
cos=1/cos;
cos=sqrt(cos);
l*=cos;
}
dmax=0;
for(k=1;k<=i;k++)
if(k!=i&&k!=1)
{
numa=(x[sol[1]]-x[sol[i]])*(y[sol[i]]-y[sol[k]])-(x[sol[i]]-x[sol[k]])*(y[sol[1]]-y[sol[i]]);
numi=(x[sol[1]]-x[sol[i]])*(x[sol[1]]-x[sol[i]])+(y[sol[1]]-y[sol[i]])*(y[sol[1]]-y[sol[i]]);
if(numa<0)numa=-numa;
numi=sqrt(numi);
d=numa/numi;
if(d>dmax)dmax=d;
}
s=dmax*l;
if(s<smax)smax=s;
g<<fixed<<setprecision(2)<<smax;
return 0;
}