Pagini recente » Cod sursa (job #2902505) | Cod sursa (job #1308016) | Cod sursa (job #2937077) | Cod sursa (job #856007) | Cod sursa (job #600809)
Cod sursa(job #600809)
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define NMAX 100005
#define pdd pair <double,double>
#define x first
#define y second
using namespace std;
int n,r,touch;
pdd A[NMAX],st[NMAX];
double rez;
bool comp(pdd a,pdd b)
{
if (a.y<b.y)
return 1;
if (a.y>b.y)
return 0;
if (a.x<b.x)
return 1;
return 0;
}
inline int semn(pdd a,pdd b,pdd c)
{
double A=a.y-b.y;
double B=b.x-a.x;
double C=a.x*b.y-b.x*a.y;
return (A*c.x+B*c.y+C)<0;
}
inline double modul(double x)
{
return x<0 ? -x : x;
}
inline double min(double x,double y)
{
return x<y ? x : y;
}
int main()
{
freopen("rubarba.in","r",stdin);
freopen("rubarba.out","w",stdout);
scanf("%d",&n);
int i,j,which;
for (i=1; i<=n; i++)
scanf("%lf%lf",&A[i].x,&A[i].y);
sort(A+1,A+n+1,comp);
st[++r]=A[1]; st[++r]=A[2];
for (i=3; i<=n; i++)
{
while (r>=2 && semn(st[r-1],st[r],A[i]))
r--;
st[++r]=A[i];
}
for (i=n-1; i>=1; i--)
{
while (r>=2 && semn(st[r-1],st[r],A[i]))
r--;
st[++r]=A[i];
}
st[0]=st[r-1]; st[r+1]=st[2];
double A,B,C,A2,B2,C2,val,val2,best,best2;
for (i=1; i<r; i++)
{
A=st[i].y-st[i+1].y;
B=st[i+1].x-st[i].x;
C=st[i].x*st[i+1].y-st[i+1].x*st[i].y;
val=sqrt(A*A+B*B); best=0;
for (j=1; j<=r; j++)
if (j!=i && j!=i+1)
{
val2=modul(A*st[j].x+B*st[j].y+C);
if (val2>best)
best=val2,which=j;
}
best/=val;
A2=-B;
B2=A;
C2=-A2*st[i-1].x-B2*st[i-1].y;
val2=sqrt(A2*A2+B2*B2);
best2=modul(A2*st[i+2].x+B2*st[i+2].y+C2)/val2;
if (!touch)
rez=best*best2,touch=1;
else
rez=min(rez,best*best2);
}
printf("%.2lf\n",rez);
return 0;
}