Pagini recente » Cod sursa (job #1505006) | Cod sursa (job #1867376) | Cod sursa (job #141289) | Cod sursa (job #2238871) | Cod sursa (job #2034858)
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define nmax 100005
using namespace std;
ifstream si("rubarba.in");
ofstream so("rubarba.out");
int n,k;
double sol=1LL*(1<<30)*(1<<30);
struct point
{
int x;
int y;
}p[nmax],s[nmax];
struct pointd
{
double x;
double y;
};
long long det(const point &a,const point &b,const point &c)
{
return (1LL*b.x-a.x)*(c.y-a.y)-(1LL*c.x-a.x)*(b.y-a.y);
}
int cmp(const point &a,const point &b)
{
return det(p[1],a,b)>0;
}
double distd(const pointd &a,const pointd &b)
{
return sqrt(((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}
void solve(point a,point b)
{
if (!(a.x<=b.x))
swap(a,b);
double m,b1,b2,dist=0;
m=(1.0*b.y-a.y)/(b.x-a.x);
b1=1.0*(1.0*a.y*(b.x-a.x)-1.0*a.x*(b.y-a.y))/(b.x-a.x);
pointd p,l,c,aux;
l.x=a.x;
l.y=a.y;
c.x=b.x;
c.y=b.y;
for(int i=1;i<=k;++i)
{
if((s[i].x!=a.x||s[i].y!=a.y)&&(s[i].x!=b.x||s[i].y!=b.y))
{
if(b.x==a.x)
{
p.x=a.x;
p.y=s[i].y;
}
else
if(b.y==a.y)
{
p.x=s[i].x;
p.y=a.y;
}
else
{
b2=s[i].y+1.0*s[i].x/m;
p.x=m*(1.0*b2-b1)/(m*m+1);
p.y=m*p.x+b1;
}
aux.x=s[i].x;
aux.y=s[i].y;
dist=max(dist,distd(aux,p));
if(b.x!=a.x)
{
if(p.x>=c.x)
c=p;
if(p.x<=l.x)
l=p;
}
else
{
c.y=max(c.y,p.y);
l.y=min(l.y,p.y);
}
}
}
sol=min(sol,dist*distd(l,c));
}
int main()
{
int j=1;
si>>n;
for(int i=1;i<=n;i++)
{
si>>p[i].x>>p[i].y;
if(p[i].y<=p[j].y||(p[i].y==p[j].y&&p[i].x<=p[j].x))
j=i;
}
swap(p[1],p[j]);
sort(p+2,p+n+1,cmp);
for(int i=1;i<=n;i++)
{
while(k>=2&&det(s[k-1],s[k],p[i])<=0)
k--;
s[++k]=p[i];
}
s[k+1]=p[1];
for(int i=1;i<=k;i++)
solve(s[i],s[i+1]);
so<<setprecision(2)<<fixed<<sol<<'\n';
return 0;
}