Pagini recente » Cod sursa (job #159729) | Cod sursa (job #118847) | Cod sursa (job #2792892) | Cod sursa (job #365863) | Cod sursa (job #32892)
Cod sursa(job #32892)
# include <stdio.h>
typedef struct PUNCT {long int x,y;};
const long int MAXN=100000; //AICI!!!! 100.000
PUNCT pct[MAXN+5];
PUNCT hull[MAXN+5];
long int n,hull_size;
void citire()
{
FILE *f=fopen("rubarba.in","r");
fscanf(f,"%ld",&n);
for (long int i=1;i<=n;i++)
fscanf(f,"%ld%ld",&pct[i].x,&pct[i].y);
fclose(f);
}
////////////////////////////////////////////////////////
// DETERMINAREA INFASURATORII CONVEXE
////////////////////////////////////////////////////////
long int det_pct_ancora()
{
long int i,min=1;
for (i=2;i<=n;i++)
if (pct[i].x<pct[min].x || (pct[i].x==pct[min].x&&pct[i].y<pct[min].y))
min=i;
return min;
}
double panta(long int i)
{
return (double)(pct[i].y-pct[1].y)/(pct[i].x-pct[1].x);
}
int panta_mai_mare(int i, int j)
{
if (pct[i].x==pct[1].x)
{
if (pct[j].x==pct[1].x)
{
if (pct[i].y>pct[j].y) return 0;
else return 1;
}
else return 1;
}
else if (pct[j].x==pct[1].x) return 0;
else //cazul NORMAL
{
if ( panta(i)>panta(j) ) return 1;
if ( panta(i)<panta(j) ) return 0;
if (pct[i].x>pct[j].x) return 1;
else return 0;
}
}
void quick(long int li, long int lf) //criteriul este panta
{
long int i=li,j=lf,ii=0,jj=-1,au;PUNCT aux;
while (i<j)
{
if (panta_mai_mare(i,j))
{
aux=pct[i];pct[i]=pct[j];pct[j]=aux;
au=ii;ii=-jj;jj=-au;
}
i+=ii;j+=jj;
}
if (i-li>1) quick (li,i-1);
if (lf-i>1) quick (i+1,lf);
}
void dequeue(long int &u)
{
while ( (hull[u-1].x-hull[u-2].x)*(hull[u].y-hull[u-2].y)-(hull[u].x-hull[u-2].x)*(hull[u-1].y-hull[u-2].y)<=0 )
{
u--;
hull[u]=hull[u+1];
}
}
void convex_hull()
{
long int ultim=3,curs=4;
hull[1]=pct[1];hull[2]=pct[2];hull[3]=pct[3];
while (curs<=n)
{
hull[++ultim]=pct[curs];
dequeue(ultim);
curs++;
}
hull_size=ultim-1;
}
void convex_hull_header()
{
long int i=det_pct_ancora();
PUNCT p;
p=pct[1];pct[1]=pct[i];pct[i]=p;
quick(2,n);
n++;pct[n]=pct[1];
convex_hull();
}
////////////////////////////////////////////////////////
// ROTATING CALIPERS
////////////////////////////////////////////////////////
double coord_orig(PUNCT p, double m)
{return p.x-p.y/m;}
double modul(double a)
{if (a>0) return a; return -a;}
double dif_max(PUNCT a, double m)
{
long int i;double difm=0,x0a,x0;
x0a=coord_orig(a,m);
for (i=1;i<=hull_size;i++)
{
x0=coord_orig(hull[i],m);
if (modul(x0-x0a)>difm) difm=modul(x0-x0a);
}
return difm;
}
double dif_max_abs(double m)
{
long int i;
double x0min,x0max,x0;
x0min=x0max=coord_orig(hull[1],m);
for (i=2;i<=hull_size;i++)
{
x0=coord_orig(hull[i],m);
if (x0<x0min) x0min=x0;
if (x0>x0max) x0max=x0;
}
return x0max-x0min;
}
long int maxy()
{
long int i;long int sol=hull[1].y;
for (i=2;i<=hull_size;i++)
if (hull[i].y>sol) sol=hull[i].y;
return sol;
}
long int miny()
{
long int i;long int sol=hull[1].y;
for (i=2;i<=hull_size;i++)
if (hull[i].y<sol) sol=hull[i].y;
return sol;
}
long int maxx()
{
long int i;long int sol=hull[1].x;
for (i=2;i<=hull_size;i++)
if (hull[i].x>sol) sol=hull[i].x;
return sol;
}
long int minx()
{
long int i;long int sol=hull[1].x;
for (i=2;i<=hull_size;i++)
if (hull[i].x<sol) sol=hull[i].x;
return sol;
}
double find_area()
{
long int i;double max_area=(double)2000*2000,area,pan,size1,size2;
for (i=1;i<hull_size;i++)
{
if ( hull[i+1].x==hull[i].x || hull[i+1].y==hull[i].y )
area=(maxy()-miny())*(maxx()-minx());
else
{
pan=(double)(hull[i+1].y-hull[i].y)/(hull[i+1].x-hull[i].x);
size1=dif_max(hull[i],pan);
size2=dif_max_abs(-1/pan);
area=size1*size2*pan/(1+pan*pan);
area=modul(area);
}
if (area<max_area) max_area=area;
}
return max_area;
}
////////////////////////////////////////////////////////
// MAIN AND INTERFACE
////////////////////////////////////////////////////////
void print_hull();
void scrie(double sol)
{
FILE *g=fopen("rubarba.out","w");
fprintf(g,"%-.2lf\n",sol);
fcloseall();
}
int main()
{
citire();
convex_hull_header();
//print_hull();
double sol=find_area();
scrie(sol);
return 0;
}
void print_hull()
{
FILE *g=fopen("hull.out","w");
for (long int i=1;i<=hull_size;i++)
fprintf(g,"%ld %ld\n",hull[i].x,hull[i].y);
fclose(g);
}