Cod sursa(job #711266)

Utilizator hunter_ionutzzzFarcas Ionut hunter_ionutzzz Data 11 martie 2012 20:05:18
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<fstream>
#include<algorithm>
using namespace std;
#define INF 1000000010
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct cel{double x, y;};
int n,i,poz,k,stv[130000];
double minx=INF,miny=INF;
cel v[130000],aux;

inline int scoate(double x1, double y1, double x2, double y2, double x3, double y3)
{long double  x = ((long double)x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);
	if(x >= 0)
		return 1;
    return 0;	
}
inline bool cmp(cel a, cel b)
{   if ((a.x * b.y) > (a.y * b.x))
		return true;
	else
		return false;
}
int main()
{   fin >> n;
	v[0].x = INF;
	v[0].y = INF;
	for(i=1;i<=n;i++)
	{   fin >> v[i].x >> v[i].y;
		if (v[i].x < v[poz].x)
			poz = i;
		else
		if (v[i].x == v[poz].x )
			if( v[i].y < v[poz].y 
				poz = i;
	}
	aux = v[poz];
	v[poz]=v[1];
	v[1]=aux;
	
	minx = v[1].x;
	miny = v[1].y;
	for(i=1;i<= n;i++)
	{   v[i].x -= minx;
		v[i].y -= miny;
	}
	sort(v+2,v+n+1,cmp);
	stv[1]=1;
	stv[2]=2; 
	k = 2;
	for(i=3;i<=n;i++)
	{	while( k>=2 && scoate(v[i].x,v[i].y,v[stv[k]].x,v[stv[k]].y,v[stv[k-1]].x,v[stv[k-1]].y) )
			k--;
		stv[++k] = i;
	}
	fout << k;
	for(i=1;i<=k;i++)
		fout << v[stv[i]].x + minx << " " << v[stv[i]].y + miny << '\n';
	return 0;
}