Cod sursa(job #561052)

Utilizator avram_florinavram florin constantin avram_florin Data 18 martie 2011 20:32:28
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include<fstream>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

const int MaxN = 120005;

struct punct{
		double x,y;
		}p[MaxN];
int n,vfs,st[2*MaxN];
vector<punct> Vans;

struct cmp
{
	bool operator()( const punct &a,const punct &b )
	{
		if( a.x != b.x )
			return a.x < b.x;
		return a.y < b.y;
	}
};

double sarrus(punct a , punct b , punct c)
{
	return a.x*b.y + b.x*c.y + c.x*a.y - b.y*c.x - b.x*a.y - a.x*c.y;
}

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" , &p[i].x , &p[i].y);
	sort(p+1,p+n+1,cmp());
	vfs = 1; st[vfs] = 1;
	st[++vfs] = 2;
	for( i = 3 ; i <= n ; i++ )
		{
			while( vfs > 1 && sarrus(p[st[vfs-1]],p[st[vfs]],p[i]) < 0 )
				vfs--;
			st[++vfs] = i;
		}
	for( i = 1 ; i <= vfs ; i++ )
		Vans.push_back(p[st[i]]);
	vfs = 1; st[vfs] = n;
	st[++vfs] = n-1;
	for( i = n-2 ; i ; i-- )
		{
			while( vfs > 1 && sarrus(p[st[vfs-1]] , p[st[vfs]] , p[i]) < 0 )
				vfs--;
			st[++vfs] = i;
		}
	for( i = 2 ; i < vfs ; i++ )
		Vans.push_back(p[st[i]]);
	vector<punct>::iterator it,iend;
	iend = Vans.end();
	it = Vans.begin();
	printf("%d\n" , Vans.size());
	for( ; it != iend ; ++it )
		printf("%lf %lf\n" , it->x , it-> y);
	return 0;
}