Pagini recente » Cod sursa (job #2362982) | Cod sursa (job #2025173) | Cod sursa (job #728978) | Cod sursa (job #2215099) | Cod sursa (job #326818)
Cod sursa(job #326818)
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<bitset>
#include<algorithm>
using namespace std;
#define mp make_pair
#define fs first
#define sc second
#define N 100010
#define pdd pair<double,double>
const double eps=1e-7;
int n,st[N];
double A,B,C,rez=-1;
pdd v[N];
bitset<N> uz;
inline char cmp(double x,double y)
{
if(x+eps<y)
return -1;
if(y+eps<x)
return 1;
return 0;
}
inline char semn(pdd a,pdd b,pdd c)
{
double A=a.sc-b.sc,B=b.fs-a.fs,C=a.fs*b.sc-b.fs*a.sc;
return cmp(A*c.fs+B*c.sc+C,0);
}
inline double modul(double x)
{
if(x<0)
return -x;
return x;
}
inline double distanta(pdd a,pdd b)
{
return sqrt((a.fs-b.fs)*(a.fs-b.fs)+(a.sc-b.sc)*(a.sc-b.sc));
}
inline void citire()
{
scanf("%d",&n);
for(int i=1; i<=n; ++i)
scanf("%lf%lf",&v[i].fs,&v[i].sc);
sort(v+1,v+n+1);
}
inline void infasuratoare()
{
int k=2;
st[1]=1;
st[2]=2;
uz[2]=1;
int pas=1,i=3;
while(uz[1]==0)
{
while(uz[i])
{
if(i==n)
pas=-1;
i+=pas;
}
while(k>1 && semn(v[st[k-1]],v[st[k]],v[i])==-1)
{
uz[st[k]]=0;
--k;
}
st[++k]=i;
uz[i]=1;
}
st[0]=k;
}
inline double afla(pdd p,double &dist)
{
double d=modul(A*p.fs+B*p.sc+C);
d*=d;
d/=(A*A+B*B);
dist=sqrt(d);
double A1=-B;
double B1=A;
double C1=A*p.sc-B*p.fs;
double x=(C1*B-C*B1)/(A*B1-A1*B);
return x;
/*double a=A*A+B*B;
double b=-2*p.fs*B*B+2*A*C+2*p.sc*A*B;
double c=-d*B*B+B*B*p.fs*p.fs+p.sc*p.sc*B*B+2*p.sc*B*C+C*C;
double delta=b*b-4*a*c;
if(cmp(delta,0)!=0)
{
//printf("Nu prea e bine :( , delta = %lf\n",delta);
exit(4);
}
double x=-b/(2*a);
dist=sqrt(d);
return x;*/
}
inline void rezolva()
{
double xmin,xmax,y;
int cy;
double s;
for(int i=1; i<st[0]; ++i)
{
A=v[st[i]].sc-v[st[i+1]].sc;
B=v[st[i+1]].fs-v[st[i]].fs;
C=v[st[i]].fs*v[st[i+1]].sc-v[st[i+1]].fs*v[st[i]].sc;
if(A!=0 && B!=0)
{
double dist;
double x=afla(v[st[1]],dist);
y=dist;
xmin=xmax=x;
cy=st[1];
for(int j=2; j<st[0]; ++j)
{
x=afla(v[st[j]],dist);
if(cmp(dist,y)==1)
{
y=dist;
cy=st[j];
}
if(cmp(x,xmin)==-1)
xmin=x;
if(cmp(x,xmax)==1)
xmax=x;
}
double ymin=(-A*xmin-C)/B;
double ymax=(-A*xmax-C)/B;
pdd aux1=mp(xmax,ymax),aux2=mp(xmin,ymin);
s=y*distanta(aux1,aux2);
}
else
if(A==0)
{
double y=-C/B;
xmin=xmax=v[st[1]].fs;
double dif=modul(v[st[1]].sc-y);
cy=st[1];
for(int j=2; j<st[0]; ++j)
{
if(v[st[j]].fs<xmin)
xmin=v[st[j]].fs;
if(v[st[j]].fs>xmax)
xmax=v[st[j]].fs;
double aux=modul(v[st[j]].sc-y);
if(cmp(aux,dif)==1)
{
dif=aux;
cy=st[j];
}
}
s=(modul(y-v[cy].sc))*(xmax-xmin);
}
else
{
double ymax,ymin;
ymax=ymin=v[st[1]].sc;
double x=-C/A;
int cx=1;
double dif=modul(v[st[1]].fs-x);
for(int j=2; j<st[0]; ++j)
{
if(v[st[j]].sc<ymin)
ymin=v[st[j]].sc;
if(v[st[j]].sc>ymax)
ymax=v[st[j]].sc;
double aux=modul(v[st[j]].fs-x);
if(cmp(aux,dif)==1)
{
dif=aux;
cx=st[j];
}
}
s=(modul(x-v[cx].fs))*(ymax-ymin);
}
if(rez==-1)
rez=s;
else
if(cmp(rez,s)==1)
rez=s;
}
printf("%lf\n",rez);
}
int main()
{
freopen("rubarba.in","r",stdin);
freopen("rubarba.out","w",stdout);
citire();
if(n<3)
{
printf("0.000000\n");
return 0;
}
infasuratoare();
//for(int i=1; i<st[0]; ++i)
// printf("%lf %lf\n",v[st[i]].fs,v[st[i]].sc);
//printf("\n");
rezolva();
return 0;
}