Cod sursa(job #407632)

Utilizator alex@ndraAlexandra alex@ndra Data 2 martie 2010 15:12:34
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;

const int MAX_N = 120010;

#define x first
#define y second
#define punct pair<double, double> 
int n;
punct a[MAX_N];
int s[MAX_N], viz[MAX_N];

int signum(punct a, punct b, punct c)
{
	return 1 - ((a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y) <= 0);
}

int main()
{
	int i, p,k;
	freopen("infasuratoare.in","r",stdin);
	   scanf("%d",&n);

	for (i = 1; i <= n; ++i)
		 scanf("%lf%lf",&a[i].x,&a[i].y);
      fclose(stdin);
       
    sort(a + 1, a + n + 1);
    k=1;
	s[k] = 1;
	
	for (i = 2, p = 1; i; i=i+ (p = (i == n) ? -p : p))
	{
		if (!viz[i])
		{
			while (k > 1 && signum(a[i], a[s[k]], a[s[k - 1]]))
				viz[s[k--]] = 0;

			viz[s[++k] = i] = 1;
		}
	}

  freopen("infasuratoare.out","w",stdout);
	printf("%d\n",k-1);	

	
	for (i = 1; i < k; ++i)
		printf("%.6lf %.6lf\n",a[s[i]].x,a[s[i]].y);
	
	fclose(stdout);
	
	return 0;
}