Cod sursa(job #460862)

Utilizator tudgal1001Profir Tudor tudgal1001 Data 4 iunie 2010 12:56:49
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include<cstdio>
#include<algorithm>
#define eps 1e-12
using namespace std;

struct ceva
{
	double x,y;
};
ceva v[120005];

double supx[120005],supy[120005],infx[120005],infy[120005],aux;
double rap,raport;
int n,i,j,ka_s,ka_i,p,cont_sup,cont_inf;

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);
	rap=(v[n].y-v[1].y)/(v[n].x-v[1].x);
	ka_s=1; ka_i=1;
	supx[1]=v[1].x;
	supy[1]=v[1].y;
	infx[1]=v[1].x;
	infy[1]=v[1].y;
	for (i=2; i<n; i++)
	{
		if (v[i].x-v[1].x==0) raport=rap+1;
		else raport=(v[i].y-v[1].y)/(v[i].x-v[1].x);
		if (raport>=rap) { ka_s++; supx[ka_s]=v[i].x; supy[ka_s]=v[i].y;  }
		else { ka_i++; infx[ka_i]=v[i].x; infy[ka_i]=v[i].y; }
	}
	ka_s++; ka_i++;
	supx[ka_s]=v[n].x;
	supy[ka_s]=v[n].y;
	infx[ka_i]=v[n].x;
	infy[ka_i]=v[n].y;
	p=1; cont_sup=ka_s;
	cont_inf=ka_i;
	for (i=2; i<ka_s; i++)
		if ((supy[i]-supy[p])/(supx[i]-supx[p])>=(supy[i+1]-supy[p])/(supx[i+1]-supx[p])) p++;
		else { supx[i]=1000000002; cont_sup--; }
	p=1;
	for (i=2; i<ka_i; i++)
		if ((infy[i]-infy[p])/(infx[i]-infx[p])<=(infy[i+1]-infy[p])/(infx[i+1]-infx[p])) p++;
		else { infx[i]=1000000002; cont_inf--; }
	printf("%d\n",cont_sup-1+cont_inf-1);
	for (i=2; i<=ka_i; i++)
		if (infx[i]!=1000000002) printf("%lf %lf\n",infx[i],infy[i]);
	for (i=ka_s-1; i>=1; i--)
		if (supx[i]!=1000000002) printf("%lf %lf\n",supx[i],supy[i]);
	return 0;
}