Cod sursa(job #693022)

Utilizator Oancea.CatalinOancea Catalin Oancea.Catalin Data 26 februarie 2012 23:21:30
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include<fstream>
#include<iomanip>
using namespace std;
#define IN "infasuratoare.in"
#define OUT "infasuratoare.out"
#define inf 1000000
#define MaxN 50000
fstream f(IN, ios::in), g(OUT, ios::out);
double x, y, Px, Py,  V, maxim;
int  last, n, i, p, R[MaxN], q;
bool ok;
struct{
	double x, y, visited;
}point[MaxN];
double compute(double x1, double y1, double x2, double y2, double x3, double y3)
{
	double R=0;
	R=x1*y2+x2*y3+x3*y1-x2*y1-x3*y2-x1*y3;
	return R;
}
int main()
{
	f>>n;
	Px=inf; Py=inf;
	for(i=1; i<=n; i++)
	{
		f>>x>>y;
		point[i].x=x; point[i].y=y; point[i].visited=0;
		if(x<Px){ Px=x; Py=y; p=i; }
		else if(x==Px && y<Py){ Px=x; Py=y; p=i; }
	}
	point[p].visited=1;
	last=p;
	q=1;
	R[q]=last;
	ok=true;
	while(ok==true)
	{
		ok=false;
		maxim=-inf;
		for(i=1; i<=n; i++)
		{
			if(point[i].visited==0 && point[i].x>=point[last].x)
			{
				ok=true;
				V=compute(point[last].x, point[last].y, point[last].x-1, point[last].y, point[i].x, point[i].y);
				if(V>maxim){ maxim=V; p=i; }
			}
		}
		if(ok==true)
		{
			last=p;
			q++; 
			R[q]=last;
			if(maxim==0)g<<"(ANT SCOS DIN CONVEX_HULL) ";
			point[p].visited=1;
		}
	}
	ok=true;
	while(ok==true)
	{
		ok=false;
		maxim=inf;
		for(i=1; i<=n; i++)
		{
			if(point[i].visited==0 && point[i].x<=point[last].x)
			{
				ok=true;
				V=compute(point[last].x, point[last].y, point[last].x-1, point[last].y, point[i].x, point[i].y);
				if(V<maxim){ maxim=V; p=i; }
			}
		}
		if(ok==true)
		{
			last=p;
			q++;
			R[q]=last;
			point[p].visited=1;
		}
	}
	g<<q<<endl;
	for(i=1; i<=q; i++)
		g<<fixed<<setprecision(12)<<point[R[i]].x<<" "<<point[R[i]].y<<"\n";
}