Cod sursa(job #891562)

Utilizator noruIlies Norbert noru Data 25 februarie 2013 17:50:21
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,vf;
typedef struct {float x,y;}NOD;
NOD st[12005],p[12005];
void citire()
{
	f>>n;
	for (int i=1;i<=n;i++)
		f>>p[i].x>>p[i].y;
}
bool cmp (NOD a, NOD b)
{
    return ((a.y < b.y) || (a.y == b.y && a.x < b.x));
}
float det(NOD a, NOD b, NOD c)
{
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
void convex_hull()
{
	sort(p+1,p+n+1,cmp);
	st[1]=p[1];
	st[2]=p[2];
	vf=2;
	int i;
	for (i=3;i<=n;i++)
	{	while (det(st[vf-1],st[vf],p[i])>0)
			vf--;
		st[++vf]=p[i];
	}
	for (i=n-1;i>=1;i--)
	{
		while (det(st[vf-1],st[vf],p[i])>0)
			vf--;
		st[++vf]=p[i];
	}
}
void afis()
{
	for (int i=vf;i>=2;i--)
		g<<(float)st[i].x<<' '<<(float)st[i].y<<'\n';
}
int main()
{
	citire();
	convex_hull();
	g<<vf<<'\n';
	afis();
	return 0;
}