Cod sursa(job #493100)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 17 octombrie 2010 10:25:13
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <stdio.h>
#include <algorithm>
#define NMAX 120005
using namespace std;
struct pct { double x,y;};
pct A[NMAX],st[NMAX];
int n,r;
bool comp(pct a,pct b)
{
	if (a.y<b.y)
		return 1;
	if (a.y>b.y)
		return 0;
	if (a.x<b.x)
		return 1;
	return 0;
}
inline int semn(pct a,pct b,pct c)
{
	double A=a.y-b.y;
	double B=b.x-a.x;
	double C=a.x*b.y-b.x*a.y;
	double val=A*c.x+B*c.y+C;
	return (val<0);
}
int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++)
		scanf("%lf%lf",&A[i].x,&A[i].y);
	sort(A+1,A+n+1,comp);
	st[++r]=A[1]; st[++r]=A[2];
	for (i=3; i<=n; i++)
	{
		while (r>=2 && semn(st[r-1],st[r],A[i])>0)
			r--;
		st[++r]=A[i];
	}
	for (i=n-1; i>=1; i--)
	{
		while (r>=2 && semn(st[r-1],st[r],A[i])>0)
			r--;
		st[++r]=A[i];
	}
	r--;
	printf("%d\n",r);
	for (i=1; i<=r; i++)
		printf("%lf %lf\n",st[i].x,st[i].y);
	return 0;
}