Cod sursa(job #625580)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 24 octombrie 2011 23:14:47
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include<fstream>
#define NMAX 120010

using namespace std;

struct punct
{
	double x, y, d;
}a[NMAX], mx;
double xx, yy;
int n, im, st[NMAX], ns=3;
	
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

void Citeste()
{
	int i;
	punct aux;
	
	f>>n>>a[1].x>>a[1].y;
	
	mx.x=a[1].x; mx.y=a[1].y; im=1;
	
	for (i=2; i<=n; ++i)
	{
		f>>a[i].x>>a[i].y;
		if (a[i].x<mx.x) mx=a[i], im=i;
		else if (a[i].x==mx.x && a[i].y<mx.y) mx=a[i], im=i;
	}
	aux=a[im];
	a[im]=a[1];
	a[1]=aux;
}

void Transleaza_Dist()
{
	int i;
	
	xx=-a[1].x;
	yy=-a[1].y;
	
	for (i=1; i<=n; ++i)
		a[i].x+=xx, a[i].y+=yy, a[i].d=a[i].x*a[i].x+a[i].y*a[i].y;
}
inline double plan(punct A,punct B,punct C)
{
	return A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-C.y*A.x-A.y*B.x;
}

int cmp(punct q, punct w)
{
	double pla=(q.x*w.y)-(q.y*w.x);
	
	if (pla<0 || pla==0 && q.d<w.d) return 0;
	return 1;
}

void Solve()
{
	int i;
	
	st[1]=1; st[2]=2; st[3]=3;
	
	
	for (i=4; i<=n; ++i)
	{
		while (plan(a[st[ns-1]], a[st[ns]], a[i])<0.0) --ns;
		if (plan(a[st[ns-1]], a[st[ns]], a[i])!=0.0) st[++ns]=i;
	}
	
	g<<ns<<"\n";
	for (i=1; i<=ns; ++i)
	{
		a[st[i]].x-=xx; a[st[i]].y-=yy;
		g<<fixed<<a[st[i]].x<<" "<<a[st[i]].y<<"\n";
		
	}
}

int main()
{
	Citeste();
	
	Transleaza_Dist();
	
	sort(a+2, a+n+1, cmp);
	
	Solve();
	
	f.close();
	g.close();
	return 0;
}