Pagini recente » Cod sursa (job #1860936) | Cod sursa (job #1159952) | Cod sursa (job #2141191) | Cod sursa (job #841038) | Cod sursa (job #2705372)
#include <bits/stdc++.h>
using namespace std;
ifstream f("rubarba.in");
ofstream g("rubarba.out");
struct wow
{
long double x,y;
}v[100005],stanga,dreapta;
int st[100005],n,q,i,ok[100005];
bool compare (wow a,wow b)
{
return a.y<b.y||(a.y==b.y&&a.x<b.x);
}
long double determinant (wow a,wow b,wow c)
{
return a.x*b.y+b.x*c.y+a.y*c.x-a.y*b.x-b.y*c.x-a.x*c.y;
}
long double distanta (wow a,wow b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
wow v2[100005];
int q2,j;
long double minim,maximx,minimx,panta,panta2,b,b2,xfin,yfin,inalt,dist,lungime;
int main()
{
f>>n;
for (i=1;i<=n;i++)
{
f>>v[i].x>>v[i].y;
}
sort (v+1,v+n+1,compare);
st[1]=1;
st[2]=2;
ok[2]=1;
q=2;
for (i=3;i<=n;i++)
{
while (q>1&&determinant(v[st[q-1]],v[st[q]],v[i])>=0)
{
ok[st[q]]=0;
st[q]=0;
q--;
}
st[++q]=i;
ok[i]=1;
}
for (i=n;i>=1;i--)
{
if (ok[i]==0)
{
while (q>1&&determinant(v[st[q-1]],v[st[q]],v[i])>=0)
{
ok[st[q]]=0;
st[q]=0;
q--;
}
st[++q]=i;
ok[i]=1;
}
}
q--;
for (i=1;i<=q;i++)
{
v2[++q2]=v[st[i]];
}
v2[q2+1]=v2[1];
q2++;
minim=1e16;
for (i=1;i<q2;i++)
{
inalt=0;
if (v2[i].x<=v2[i+1].x)
{
stanga=v2[i];
dreapta=v2[i+1];
}
else
{
stanga=v2[i+1];
dreapta=v2[i];
}
for (j=1;j<=q2-1;j++)
{
if (v2[i].x==v2[i+1].x)
{
dist=abs(v2[j].x-v2[i].x);
xfin=v2[i].x;
yfin=v2[j].y;
}
else
if (v2[i].y==v2[i+1].y)
{
dist=abs(v2[j].y-v2[i].y);
xfin=v2[j].x;
yfin=v2[i].y;
}
else
{
panta=(v2[i].y-v2[i+1].y)/(v2[i].x-v2[i+1].x);
b=v2[i].y-panta*v2[i].x;
panta2=-1/panta;
b2=v2[j].y-panta2*v2[j].x;
xfin=(b2-b)/(panta-panta2);
yfin=panta*xfin+b;
dist=distanta(wow{xfin,yfin},v2[j]);
}
inalt=max(inalt,dist);
if (xfin<stanga.x)
{
stanga=wow{xfin,yfin};
}
if (xfin>dreapta.x)
{
dreapta=wow{xfin,yfin};
}
}
lungime=distanta(stanga,dreapta);
if (inalt*lungime<minim)
{
minim=inalt*lungime;
}
}
g<<fixed<<setprecision(2)<<minim;
return 0;
}