Pagini recente » Cod sursa (job #104054) | Cod sursa (job #2055082) | Cod sursa (job #720936) | Cod sursa (job #472238) | Cod sursa (job #113595)
Cod sursa(job #113595)
using namespace std;
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define Nmax 100005
struct punct { long long x,y; };
int N;
int inf[Nmax],nr;
double Smax;
punct P[Nmax];
inline double modul(double a) { return a>=0?a:-a; }
void citire()
{
int i;
freopen("rubarba.in","r",stdin);
scanf("%d",&N);
for (i=1;i<=N;++i)
scanf("%lld %lld",&P[i].x,&P[i].y);
fclose(stdout);
}
void qsort(int st,int dr)
{
int i=st,j=dr;
punct m=P[(st+dr)>>1],aux;
while (i<=j)
{
while ( (double)(P[i].x-P[1].x)/(P[i].y-P[1].y)>(double)(m.x-P[1].x)/(m.y-P[1].y) ) ++i;
while ( (double)(P[j].x-P[1].x)/(P[j].y-P[1].y)<(double)(m.x-P[1].x)/(m.y-P[1].y) ) --j;
if (i<=j)
{
aux=P[i];
P[i]=P[j];
P[j]=aux;
++i;
--j;
}
}
if (i<dr) qsort(i,dr);
if (st<j) qsort(st,j);
}
int intoarcere(int A,int B,int C)
{
long long aa,bb,cc;
aa=P[A].y-P[B].y;
bb=P[B].x-P[A].x;
cc=P[A].x*P[B].y-P[B].x*P[A].y;
if (aa*P[C].x+bb*P[C].y+cc<=0) return 1;
return 0;
}
void infasuratoare()
{
int i,start=1;
punct aux;
for (i=2;i<=N;++i)
if ( (P[i].y<P[start].y) || ( (P[i].y==P[start].y) && (P[i].x<P[start].x) ) )
start=i;
aux=P[1];P[1]=P[start];P[start]=aux;
start=1;
for (i=2;i<=N;++i)
if (P[i].y==P[1].y)
{
++start;
aux=P[i];
P[i]=P[start];
P[start]=aux;
}
qsort(start+1,N);
nr=3;
inf[1]=1;inf[2]=2;inf[3]=3;
i=4;
while (i<=N)
{
inf[++nr]=i;
while ( (nr>3)&&(intoarcere(inf[nr-2],inf[nr-1],inf[nr])) ) inf[--nr]=i;
++i;
}
for (i=1;i<=nr;++i)
P[i]=P[inf[i]];
P[nr+1]=P[1];
}
void aria()
{
int i,j;
double d,S,x,h,d1,d2;
double hmax,min,max;
for (i=1;i<=nr;++i)
{
d=((double)(P[i].x-P[i+1].x)*(P[i].x-P[i+1].x)+(P[i].y-P[i+1].y)*(P[i].y-P[i+1].y) );
max=d;
d=sqrt(d);
hmax=min=0;
for (j=1;j<=nr;++j)
if ((j!=i)&&(j!=i+1))
{
S=(double)P[i].x*P[i+1].y+P[i+1].x*P[j].y+P[j].x*P[i].y-P[i].y*P[i+1].x-P[i+1].y*P[j].x-P[j].y*P[i].x;
h=modul((double)S/d);
hmax=h>hmax?h:hmax;
x=(double)(P[i].x-P[j].x)*(P[i].x-P[j].x)+(P[i].y-P[j].y)*(P[i].y-P[j].y);
d1=(x-h*h);
x=(double)(P[i+1].x-P[j].x)*(P[i+1].x-P[j].x)+(P[i+1].y-P[j].y)*(P[i+1].y-P[j].y);
d2=(x-h*h);
//if (modul(d1+d2-d)<0.00000001) continue;
if ((d*d<d1+0.0000000001) || (d*d<d2+0.0000000001))
if (d1<d2) min=min>d1?min:d1;
else max=max>d1?max:d1;
}
min=sqrt(min);
max=sqrt(max);
if ((max+min)*hmax<Smax) Smax=(max+min)*hmax;
}
}
int main()
{
citire();
if (N>2)
{
infasuratoare();
Smax=100000000*100000000;
aria();
}
else Smax=0;
freopen("rubarba.out","w",stdout);
printf("%.2lf",Smax);
fclose(stdout);
return 0;
}