Cod sursa(job #626050)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 26 octombrie 2011 10:53:48
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include<fstream>
#include<iomanip>
#include<iostream>
#include<algorithm>
#define NMAX 120010

using namespace std;

struct punct
{
	double x, y, d;
}a[NMAX], b[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=plan(a[1], q, w);
	
	if (pla<0 || (pla==0 && q.d<w.d)) return 0;
	return 1;
}

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

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