Pagini recente » Cod sursa (job #2864727) | Cod sursa (job #5868) | Cod sursa (job #2064271) | Cod sursa (job #2300858) | Cod sursa (job #725693)
Cod sursa(job #725693)
#include<fstream>
#include<algorithm>
#include<cmath>
#define x first
#define y second
using namespace std;
const char iname[]="rubarba.in";
const char oname[]="rubarba.out";
const int maxn=100005;
ifstream f(iname);
ofstream g(oname);
typedef pair<int,int> point;
point a[maxn];
int i,j,n,k,step,h[maxn*2],been[maxn],maxd,maxl,maxr;
long long area(point a,point b,point c)
{
long long areax=1LL*a.x*(b.y-c.y)+1LL*b.x*(c.y-a.y)+1LL*c.x*(a.y-b.y);
return areax;
}
long long mod(long long a)
{
if(a<0)
return -a;
return a;
}
long long dep(point a,point b,point c)
{
long long depx = -1LL*(a.x-b.x)*(a.x-b.x)-1LL*(a.y-b.y)*(a.y-b.y)-1LL*(b.x-c.x)*(b.x-c.x)-1LL*(b.y-c.y)*(b.y-c.y)+1LL*(c.x-a.x)*(c.x-a.x)+1LL*(c.y-a.y)*(c.y-a.y);
return depx;
}
double dis(point a,point b)
{
return sqrt(1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y));
}
double minarea=1e26,areax;
int main()
{
f>>n;
for(i=1;i<=n;++i)
f>>a[i].x>>a[i].y;
sort(a+1,a+n+1);
step=1;
h[0]=1;
h[1]=2;
k=1;
been[2]=1;
i=3;
while(been[1]==0)
{
if(i==n)
step=-1;
while(been[i])
i+=step;
while(k&&area(a[h[k-1]],a[h[k]],a[i])<=0)
been[h[k--]]=0;
been[h[++k]=i]=1;
}
for(i=1;i<=k;++i)
h[i+k]=h[i];
for(i=0;i<k;++i)
{
maxd=maxr=maxl=0;
for(step=1;step<k;step<<=1);
for(j=i+1;step;step>>=1)
if(j+step<i+k&&area(a[h[i]],a[h[i+1]],a[h[j+step]])>=area(a[h[i]],a[h[i+1]],a[h[j+step-1]]))
j+=step;
maxd=j;
for(step=1;step<k;step<<=1);
for(j=i+1;step;step>>=1)
if(j+step<=maxd&&dep(a[h[i]],a[h[i+1]],a[h[j+step]])>dep(a[h[i]],a[h[i+1]],a[h[j+step-1]]))
j+=step;
maxr=j;
for(step=1;step<k;step<<=1);
for(j=maxd;step;step>>=1)
if(j+step<=i+k&&dep(a[h[i+1]],a[h[i]],a[h[j+step]])>dep(a[h[i+1]],a[h[i]],a[h[j+step-1]]))
j+=step;
maxl=j;
areax=dep(a[h[i]],a[h[i+1]],a[h[maxr]])+dep(a[h[i+1]],a[h[i]],a[h[maxl]]);
areax/=2.0*dis(a[h[i]],a[h[i+1]]);
areax+=dis(a[h[i]],a[h[i+1]]);
areax*=(1.0*area(a[h[i]],a[h[i+1]],a[h[maxd]]))/dis(a[h[i]],a[h[i+1]]);
if(areax<minarea)
minarea=areax;
}
g.setf(ios::fixed,ios::floatfield);
g.precision(2);
g<<minarea<<"\n";
f.close();
g.close();
return 0;
}