Cod sursa(job #626379)

Utilizator lianaliana tucar liana Data 26 octombrie 2011 23:02:50
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
#define nmax 120005
#define inf 1000000005
struct punct {double x, y;};
punct v[nmax], st[nmax], o;
long i, n, sf;
double difax, difay, difbx, difby, pa, pb;

void citire()
{
	o.y=inf;	o.x=inf;
	scanf("%ld",&n);
	for (i=1;i<=n;i++)
	{
		scanf("%lf %lf",&v[i].x,&v[i].y);
		if ((v[i].x<o.x)||((v[i].x==o.x)&&(v[i].y<o.y)))
			{o=v[i];	v[i]=v[1];	v[1]=o;	}
	}
}

bool cmp(punct a, punct b)
{
	difay=a.y-o.y;	difax=a.x-o.x;
	difby=b.y-o.y;	difbx=b.x-o.x;
	if (difax==0)	
		pa=inf;
	else
		pa=difay/difax;
	if (difay==0)		
		pa=0;
	if (difbx==0)		
		pb=inf;
	else
		pb=difby/difbx;
	if (difby==0)
		pb=0;
	return (pa<pb);
}

void rezolvare()
{
	st[1]=v[1];	st[2]=v[2];	st[3]=v[3];sf=3;
	for (i=4;i<=n;i++)
	{
		while ((sf>=3)&&(st[sf-1].x*st[sf].y + st[sf].x*v[i].y + v[i].x*st[sf-1].y  -  st[sf].y*v[i].x - v[i].y*st[sf-1].x - st[sf-1].y*st[sf].x<0))
			sf--;
		st[++sf]=v[i];
	}
	printf("%ld\n",sf);
	for (i=2;i<=sf;i++)
		printf("%lf %lf\n",st[i].x,st[i].y);
	printf("%lf %lf\n",st[1].x,st[1].y);
}

int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	citire();
	sort(v+2,v+1+n,cmp);
	rezolvare();
	return 0;
}