Cod sursa(job #702340)

Utilizator Eugen01Vasilescu Eugen Eugen01 Data 1 martie 2012 21:07:57
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<stdio.h>
#include<algorithm>
#define Nmax 120009
#define mp make_pair
#define x first
#define y second
#define ER 1e-12

using namespace std;

int q=1,n,i,nr,ok[Nmax],Q[Nmax];
pair<double,double> p[Nmax];

inline double abs(double x)
{
	if (x<0) return -x;
	return x;
}

int semn(pair<double,double> a,pair<double,double> b,pair<double,double> c)
{
	double A=b.y-a.y;
	double B=a.x-b.x;
	double C=a.y*b.x-a.x*b.y;
	
	if (A*c.x+B*c.y+C+ER>0) return -1;
	return 0;
}

int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	
	scanf("%d",&n);
	
	for (i=1;i<=n;i++)
		scanf("%lf%lf",&p[i].x,&p[i].y);
	
	sort(p+1,p+n+1);
	
	nr=2;
	Q[1]=1;Q[2]=2;
	ok[2]=1;
	i=3;
	
	while (!ok[1])
	{
		while (ok[i])
		{
			if (i==n) q=-1;
			i+=q;
		}
		while (nr>=2 && semn(p[Q[nr]],p[Q[nr-1]],p[i])==-1)
		{
			ok[Q[nr]]=0;
			nr--;
		}
		nr++;
		Q[nr]=i;
		ok[i]=1;
	}
	nr--;
	printf("%d\n",nr);
	for (i=1;i<=nr;i++)
		printf("%lf %lf\n",p[Q[i]].x,p[Q[i]].y);
}