Cod sursa(job #1334842)

Utilizator ducu34Albastroiu Radu Gabriel ducu34 Data 4 februarie 2015 18:44:03
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int i,n,viz[100001],stiva[100001],x,k;
struct infas
{
	double x,y;
}v[120001];
int cmp(infas A,infas B)
{
	if(A.x==B.x)
		return A.y<B.y;
	else
		return A.x<B.x;
}
double determinant(int A,int B,int C)
{
	return (v[B].x-v[A].x)*(v[C].y-v[A].y)-(v[C].x-v[A].x)*(v[B].y-v[A].y);
}
void parcurgere(int x)
{
	for(int i=1;i<=n;i++)
	{
		if(!viz[i])
		{
			viz[i]=1;
			double z=determinant(stiva[x-1],stiva[x],i);
			if(z < 0)
			{
				x++;k=x;
				stiva[x]=i;
				//parcurgere(x);
			}
			else
			{
				while(determinant(stiva[x-1],stiva[x],i)>0 && x>=1)
				{
					viz[stiva[x]]=0;
					x--;
					
				}viz[i]=1;stiva[++x]=i;
			}
				//parcurgere(x);
		}
	}
}
void parcurgere2()
{
	for(int i=n;i>0;i--)
	{
		if(!viz[i])
		{
			viz[i]=1;
			double z=determinant(stiva[x-1],stiva[x],i);
			if(z < 0)
			{
				x++;k=x;
				stiva[x]=i;
				//parcurgere(x);
			}
			else
			{
				while(determinant(stiva[x-1],stiva[x],i)>0 && x>=1)
				{
					viz[stiva[x]]=0;
					x--;
					
				}viz[i]=1;stiva[++x]=i;
			}
				//parcurgere(x);
		}
	}
}
int main()
{
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>v[i].x>>v[i].y;
	sort(v+1,v+n+1,cmp);
	stiva[1]=1;stiva[2]=2;viz[2]=1;
	parcurgere(2);
	parcurgere2();
	for(i=x-1;i>0;i--)
		fout<<v[stiva[i]].x<<" "<<v[stiva[i]].y<<"\n";
	return 0;
}