Pagini recente » Cod sursa (job #2806645) | Cod sursa (job #715980) | Cod sursa (job #1175672) | Cod sursa (job #3192790) | Cod sursa (job #1779746)
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <cmath>
#define x first
#define y second
#define MAX_N 120005
#define inf 1e9
using namespace std;
typedef pair<float, float> Point;
const double EPS = 1e-12;//10^(-12)
ifstream f("rubarba.in");
ofstream g("rubarba.out");
int n,p,i,xmin,xmax,ymin,ymax,j;
float arie,ariemin,panta,panta2,c,b,cmin,cmax,bmin,bmax;
Point v[MAX_N],m,m2,m3,m4;
bool vis[MAX_N];
int st[MAX_N], head;
float prod(Point O, Point A, Point B) {
return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}
int main()
{
f>> n;
for ( i = 1; i <= n; ++i)
f >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1);
st[1] = 1; st[2] = 2; head = 2;
vis[2] = true;
for (i = 1, p = 1; i > 0; i +=p )
{
if(i==n) p=-1;
if (vis[i]) continue;
while (head >= 2 && prod(v[st[head - 1]], v[st[head]], v[i]) < EPS)
vis[st[head--]] = false;
st[++head] = i;
vis[i] = true;
}
xmin=ymin=10000000; xmax=ymax=-1;
for(i=1;i<head;i++)
{
if(v[st[i]].x<xmin) xmin=v[st[i]].x;
if(v[st[i]].x>xmax) xmax=v[st[i]].x;
if(v[st[i]].y<ymin) ymin=v[st[i]].y;
if(v[st[i]].y>ymax) ymax=v[st[i]].y;
}
ariemin=(xmax-xmin)*(ymax-ymin);
ariemin=ariemin*ariemin;
for(i=1;i<head;i++)
{
if(v[st[i]].x!=v[st[i]+1].x)
{
panta=(v[st[i+1]].y-v[st[i]].y)/(v[st[i+1]].x-v[st[i]].x);
panta2=-1/panta;
cmin=bmin=inf; cmax=bmax=-inf;
for(j=1;j<head;j++)
{
c=(v[st[j]].y-panta*v[st[j]].x);
b=(v[st[j]].y-panta2*v[st[j]].x);
if(c<cmin) cmin=c;
if(c>cmax) cmax=c;
if(b<bmin) bmin=b;
if(b>bmax) bmax=b;
}
arie=(cmax-cmin)/sqrt(1+panta*panta)*((bmax-bmin)/sqrt(1+panta2*panta2));
if(arie<ariemin) ariemin=arie;
}
}
g<<fixed<<setprecision(2)<<ariemin<<'\n';
return 0;
}