Cod sursa(job #32879)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 18 martie 2007 17:22:37
Problema Rubarba Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.22 kb
# 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, long int j)
{
return (pct[i].y-pct[j].y)/(pct[i].x-pct[j].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,1)>panta(j,1) ) return 1;
	if ( panta(i,1)<panta(j,1) ) 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);
}