Pagini recente » Cod sursa (job #2871902) | Borderou de evaluare (job #2177394) | Cod sursa (job #2985253) | Borderou de evaluare (job #1117524) | Cod sursa (job #1779038)
#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<double, double> 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;
double 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;
double prod(Point O, Point A, Point B) {
return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}
double dist(double panta, int n1, int n2)
{
return abs( (n1-n2)*1.0/(sqrt((1.0)*(1.0+panta*panta))));
}
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);
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)*1.0/(v[st[i+1]].x-v[st[i]].x);
panta2=(-1.0)/panta;
cmin=bmin=inf; cmax=bmax=-inf;
for(j=1;j<head;j++)
{
c=abs(v[st[j]].y-panta*v[st[j]].x);
b=abs(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=dist(panta,cmin,cmax)*dist(panta2,bmin,bmax);
if(arie<ariemin) ariemin=arie;
}
}
g<<ariemin<<'\n';
return 0;
}