Cod sursa(job #696376)

Utilizator soriynSorin Rita soriyn Data 28 februarie 2012 18:18:32
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<cstdio>
#include<algorithm>
#define maxn 120010
#define inf 1<<30

using namespace std;
double X[maxn],Y[maxn];
int ST[maxn],IND[maxn],n,PI;

bool cmp(int i,int j)
{
	return (double)((Y[j]-Y[PI])*(X[i]-X[PI]))<(double)((X[j]-X[PI])*(Y[i]-Y[PI]));
}
long double semn(int i1,int i2,int i3)
{
	return (long double)(X[i1]*Y[i2]+X[i2]*Y[i3]+X[i3]*Y[i1]-X[i3]*Y[i2]-X[i1]*Y[i3]-X[i2]*Y[i1]);
}

void read()
{
	freopen("infasuratoare.in","r",stdin);
	scanf("%d",&n);
	X[0]=inf,Y[0]=inf;
	PI=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%lf %lf",&X[i],&Y[i]);
		if(X[i]<X[PI] || ( X[i]==X[PI] && Y[i]<Y[PI])) PI=i;
	}
	for(int i=1;i<=n;i++)
	{
		if(i==PI) continue;
	    IND[++IND[0]]=i;
	}
}
void solve()
{
	ST[++ST[0]]=PI;
	sort(IND+1,IND+IND[0]+1,cmp);
	for(int i=1;i<=IND[0];i++)
	{
		if(IND[i]==PI) continue;
		while(ST[0]>=2 && semn(ST[ST[0]-1],ST[ST[0]],IND[i]) >0 ) --ST[0];
		ST[++ST[0]]=IND[i];
	}
}
int main()
{
	freopen("infasuratoare.out","w",stdout);
	read();
	solve();
	printf("%d\n",ST[0]);
	for(int i=ST[0];i>=1;i--)
	{
		printf("%lf %lf\n",X[ST[i]],Y[ST[i]]);
	}
}