Cod sursa(job #261770)

Utilizator c_iulyanCretu Iulian c_iulyan Data 18 februarie 2009 19:22:09
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include<cstdio>
#include<algorithm>
#define MX 120001
#define oo 100000001
#include<vector>
using namespace std;

struct pct
{
double x,y;
long double panta;

bool operator!=(pct a)
	{
	return x==a.x&&y==a.y?0:1;
	}
bool operator==(pct a)
	{
	return x==a.x&&y==a.y?1:0;
	}
};

pct a[MX],mn;
long n,k=1;
pct s[MX];

long double sm(pct a,pct b, pct c)
{
return (long double)(a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-b.x*a.y-a.x*c.y);
}

void rd()
{
mn.x=mn.y=oo;
scanf("%ld",&n);
for(long i=1;i<=n;i++)
{
	double x,y;
	scanf("%lf%lf",&x,&y);	
	a[i].x=x,a[i].y=y;
	if(mn.x>a[i].x)
		mn=a[i];
	else if(mn.x==a[i].x&&mn.y>a[i].y)
		mn=a[i];
	}
}

bool cmp(pct a,pct b)
{
return (long double)(a.y-mn.y)*(b.x-mn.x)<(long double)(a.x-mn.x)*(b.y-mn.y);
}

void go()
{
s[1]=mn;
	
for(long i=1;i<=n;i++)
	if(a[i]!=mn)
		{
		long double x=sm(s[k-1],s[k],a[i]);
		while(k>=2&&x<0)
			{
			k--;
			x=sm(s[k-1],s[k],a[i]);
			}
		s[++k]=a[i];
		}
}

void afisare()
{
printf("%ld\n",k);
for(long i=1;i<=k;i++)
	printf("%lf %lf\n",s[i].x,s[i].y);	
}

void kk1()
{
for(long i=1;i<=n;i++)
	a[i].panta=(long double)(a[i].x-mn.x==0?0:(long double)(a[i].y-mn.y)/(a[i].x-mn.x));
}

bool ckk(pct a,pct b)
{
return a.panta<b.panta;
}

int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);

rd();

kk1();
sort(a+1,a+n+1,ckk);


//sort(a+1,a+n+1,cmp);

go();
afisare();

	
return 0;
}