Cod sursa(job #731544)

Utilizator HulkIncredibilul Hulk Hulk Data 8 aprilie 2012 13:29:46
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

#define pi pair<double,double>
#define x first
#define y second
#define NMAX 120005
#define eps 0.000000000001

pi v[NMAX];
int st[NMAX],n,sf;
char viz[NMAX];

inline int semn(pi A,pi B,pi C)
{
	double a = B.y - A.y;
	double b = A.x - B.x;
	double c = A.y * B.x - B.y * A.x;
	
	return C.x * a + C.y * b + c < 0;
}

inline int cmp(const pi& a,const pi& b)
{
	if(a.y + eps > b.y && a.y - eps < b.y)
		return a.x < b.x;
	return a.y < b.y;
}

int main ()
{
	int i;
	
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	
	scanf("%d", &n);
	for(i = 1; i <= n; i++)
		scanf("%lf%lf", &v[i].x, &v[i].y);
		
	sort(v + 1,v + n + 1,cmp);	
	
	for(i = 1; i <= n; i++)
	
	st[1] = 1;
	st[2] = 2;
	sf = 2;
	for(i = 3; i <= n; i++)
	{
		while(sf > 1 && semn(v[st[sf - 1]], v[st[sf]], v[i]))
			sf--;
		st[++sf] = i;	
	}
	
	for(i = 1; i <= sf; i++)
		viz[st[i]] = 1;
	viz[st[1]] = 0;
	
	for(i = n; i >= 1; i--)	
		if(!viz[i])
		{
			while(sf > 1 && semn(v[st[sf - 1]], v[st[sf]], v[i]))
				sf--;
			st[++sf] = i;	
		}
		
	printf("%d\n",sf - 1);	
	for(i = sf; i > 1; i--)
		printf("%.6lf %.6lf\n",v[st[i]].x,v[st[i]].y);
	
	return 0;
}

;