Cod sursa(job #260200)

Utilizator c_iulyanCretu Iulian c_iulyan Data 16 februarie 2009 19:45:21
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<cstdio>
#include<algorithm>
#define MX 120001
#define oo 100000001
#include<vector>
using namespace std;

struct pct
{
double x,y;
double p(pct m)
	{
	return (double)(y-m.y)/(double)(x-m.x);
	}
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];

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

void rd()
{
mn.x=mn.y=oo;
scanf("%ld",&n);
for(long i=1;i<=n;i++)
{
	float x,y;
	scanf("%f%f",&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 a.p(mn)<b.p(mn);
}

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

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

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

rd();
sort(a+1,a+n+1,cmp);
go();
afisare();
	
return 0;
}