Pagini recente » Cod sursa (job #3473) | Cod sursa (job #3275828) | Cod sursa (job #2031537) | Cod sursa (job #1985256) | Cod sursa (job #599266)
Cod sursa(job #599266)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
const char InFile[]="rubarba.in";
const char OutFile[]="rubarba.out";
const int MaxN=100111;
const double FINF=1.0e64;
ifstream fin(InFile);
ofstream fout(OutFile);
struct Vector2
{
Vector2(double x=0, double y=0):x(x),y(y){}
Vector2 operator- (Vector2 v)
{
return Vector2(x-v.x,y-v.y);
}
double operator* (Vector2 v)
{
return x*v.x+y*v.y;
}
void normalize()
{
double d=sqrt(x*x+y*y);
if(d)
{
x/=d;
y/=d;
}
}
void rotate90()
{
double tx(x),ty(y);
x=-ty;
y=tx;
}
double x,y;
};
typedef Vector2 Point2D;
int N,S[MaxN];
Point2D p[MaxN];
inline double sqrdist(const Point2D &a, const Point2D &b)
{
double dx=a.x-b.x;
double dy=a.y-b.y;
return dx*dx+dy*dy;
}
struct cmp
{
inline bool operator() (const Point2D &a, const Point2D &b)
{
double left=(a.y-p[1].y)*(b.x-p[1].x);
double right=(b.y-p[1].y)*(a.x-p[1].x);
if(left==right)
{
return sqrdist(a,p[1])>sqrdist(b,p[1]);
}
return left<right;
}
};
inline double det(Point2D &a, Point2D &b, Point2D &c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
inline int sgn(double x)
{
if(x==0)
{
return 0;
}
if(x<0)
{
return -1;
}
return 1;
}
inline void convexhull()
{
int ind=0;
p[0].x=p[0].y=FINF;
for(register int i=1;i<=N;++i)
{
if(p[i].y<p[ind].y)
{
ind=i;
}
else if(p[i].y==p[ind].y && p[i].x<p[ind].x)
{
ind=i;
}
}
swap(p[1],p[ind]);
sort(p+2,p+N+1,cmp());
S[0]=2;
S[1]=1;
S[2]=2;
for(register int i=3;i<=N;++i)
{
while(S[0]>=2 && sgn(det(p[S[S[0]-1]],p[S[S[0]]],p[i]))==-1)
{
--S[0];
}
S[++S[0]]=i;
}
while(S[0]>3 && sgn(det(p[S[S[0]-1]],p[S[S[0]]],p[1]))==0)
{
--S[0];
}
N=S[0];
for(register int i=1;i<=S[0];++i)
{
p[i]=p[S[i]];
}
}
inline int next(const int &index)
{
if(index==N)
{
return 1;
}
return index+1;
}
inline double mera()
{
double sol=FINF;
for(register int i=1;i<=N;++i)
{
Vector2 dir=p[next(i)]-p[i];
dir.normalize();
Vector2 pdir=dir;
pdir.rotate90();
double minc=FINF,maxc=-FINF;
double d=-FINF;
for(register int j=1;j<=N;++j)
{
Vector2 pos=p[j]-p[i];
double coord=dir*pos;
minc=min(minc,coord);
maxc=max(maxc,coord);
d=max(d,abs(pdir*pos));
}
sol=min(sol,(maxc-minc)*d);
}
return sol;
}
int main()
{
fin>>N;
for(register int i=1;i<=N;++i)
{
fin>>p[i].x>>p[i].y;
}
fin.close();
convexhull();
fout<<setprecision(2)<<fixed<<mera();
fout.close();
return 0;
}