Cod sursa(job #461897)

Utilizator tudgal1001Profir Tudor tudgal1001 Data 8 iunie 2010 23:39:50
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.93 kb
#include<cstdio>
#include<algorithm>
#define eps 1e-12
#define NMax 120005
#define ha 1000000005
using namespace std;

struct ceva
{
	double x,y;
};
ceva v[NMax];
ceva sup[NMax],inf[NMax];
ceva st_s[NMax],st_i[NMax];

double aux;
double rap,raport,rap1,rap2;
int n,i,j,ka_s,ka_i,p,cont_sup,cont_inf,ka_ss,ka_ii,u,cont_i,cont_s;

int compar (double a,double b)
{
	if (a+eps<b) return -1;
	if (b+eps<a) return 1;
	return 0;
}

int cmp (const ceva& a,const ceva& b)
{
	if(!compar(a.x,b.x)) 
		return (compar(a.y,b.y)==-1);
	return (compar(a.x,b.x)==-1);
}

int main ()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	for (i=1; i<=n; i++)
		scanf("%lf%lf",&v[i].x,&v[i].y);
	sort(v+1,v+n+1,cmp);
	ka_s=1; ka_i=1;
	raport=(v[n].y-v[1].y)/(v[n].x-v[1].x);
	for (i=2; i<n; i++)
	{
		rap=(v[i].y-v[1].y)/(v[i].x-v[1].x);
		if (rap>=raport) { sup[++ka_s].x=v[i].x; sup[ka_s].y=v[i].y; }
		else { inf[++ka_i].x=v[i].x; inf[ka_i].y=v[i].y; }
	}
	inf[1].x=v[1].x;
	inf[1].y=v[1].y;
	sup[1].x=v[1].x;
	sup[1].y=v[1].y;
	inf[++ka_i].x=v[n].x;
	inf[ka_i].y=v[n].y;
	sup[++ka_s].x=v[n].x;
	sup[ka_s].y=v[n].y;
	/*for (i=1; i<=ka_s; i++)
		printf("%lf %lf\n",sup[i].x,sup[i].y);
	printf("\n");
	for (i=1; i<=ka_i; i++)
		printf("%lf %lf\n",inf[i].x,inf[i].y);*/
	st_i[1].x=v[1].x;
	st_i[1].y=v[1].y;
	ka_ii=1;
	p=1;
	for (i=2; i<ka_i; i++)
	{
		//printf("%d %d %d\n",p,i,i+1);
		rap1=(inf[i].y-inf[p].y)/(inf[i].x-inf[p].x);
		rap2=(inf[i+1].y-inf[p].y)/(inf[i+1].x-inf[p].x);
		if (rap1<=rap2) { st_i[++ka_ii].x=inf[i].x; st_i[ka_ii].y=inf[i].y; p++; }
	}
	st_i[++ka_ii].x=v[n].x;
	st_i[ka_ii].y=v[n].y;
	cont_i=ka_ii;
	p=1; u=3;
	for (i=2; i<ka_ii; i++)
		if (st_i[i].x!=ha)
		{
			u=i+1; p=i-1;
			while (st_i[p].x==ha) p--;
			while (st_i[u].x==ha) u++;
			rap1=(st_i[i].y-st_i[p].y)/(st_i[i].x-st_i[p].x);
			rap2=(st_i[u].y-st_i[p].y)/(st_i[u].x-st_i[p].x);
			if (rap1>rap2)
			{
				st_i[i].x=ha;
				i-=2;
				cont_i--;
			}
		}
	st_s[1].x=v[1].x;
	st_s[1].y=v[1].y;
	ka_ss=1;
	p=1;
	for (i=2; i<ka_s; i++)
	{
		//printf("%d %d %d\n",p,i,i+1);
		rap1=(sup[i].y-sup[p].y)/(sup[i].x-sup[p].x);
		rap2=(sup[i+1].y-sup[p].y)/(sup[i+1].x-sup[p].x);
		if (rap1>=rap2) { st_s[++ka_ss].x=sup[i].x; st_s[ka_ss].y=sup[i].y; p++; }
	}
	st_s[++ka_ss].x=v[n].x;
	st_s[ka_ss].y=v[n].y;
	cont_s=ka_ss;
	p=1; u=3;
	for (i=2; i<ka_ss; i++)
		if (st_s[i].x!=ha)
		{
			u=i+1; p=i-1;
			while (st_s[p].x==ha) p--;
			while (st_s[u].x==ha) u++;
			rap1=(st_s[i].y-st_s[p].y)/(st_s[i].x-st_s[p].x);
			rap2=(st_s[u].y-st_s[p].y)/(st_s[u].x-st_s[p].x);
			if (rap1<rap2)
			{
				st_s[i].x=ha;
				i-=2;
				cont_s--;
			}
		}
	printf("%d\n",cont_i+cont_s-2);
	for (i=1; i<=ka_ii; i++)
		if (st_i[i].x!=ha) printf("%lf %lf\n",st_i[i].x,st_i[i].y);
	for (i=ka_ss-1; i>=2; i--)
		if (st_s[i].x!=ha) printf("%lf %lf\n",st_s[i].x,st_s[i].y);
	return 0;
}