Pagini recente » Cod sursa (job #1143597) | Cod sursa (job #780000) | Cod sursa (job #334723) | Cod sursa (job #73788) | Cod sursa (job #2705394)
#include <bits/stdc++.h>
using namespace std;
ifstream f("rubarba.in");
ofstream g("rubarba.out");
struct wow
{
long double x,y;
}v[200005],stanga,dreapta;
int st[200005],n,q,i,ok[200005];
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[200005],stk[200005];
wow min1(wow a, wow b)
{
if (a.x < b.x)
{
return a;
}
if (b.x < a.x)
{
return b;
}
if (a.y < b.y)
{
return a;
}
else
{
return b;
}
}
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;
}
for (i=2;i<=n;i++)
{
if (v[i].x==min1(v[i],v[1]).x&&v[i].y==min1(v[i],v[1]).y)
{
swap(v[1],v[i]);
}
}
sort (v+2,v+n+1,compare);
v[n+1]=v[1];
for (i=1;i<=n+1;i++)
{
while (q>=2&&determinant(stk[q-1],stk[q],v[i])<=0)
{
q--;
}
stk[++q]=v[i];
}
q--;
for (i=1;i<=q;i++)
{
v2[++q2]=stk[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)
{
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);
}
else
{
if (v2[i].y<=v2[i+1].y)
{
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.y)
{
stanga=wow{xfin,yfin};
}
if (xfin>dreapta.y)
{
dreapta=wow{xfin,yfin};
}
}
lungime=distanta(stanga,dreapta);
}
if (inalt*lungime<minim)
{
minim=inalt*lungime;
}
}
g<<fixed<<setprecision(2)<<minim;
return 0;
}