Cod sursa(job #412482)

Utilizator tiriplicamihaiTiriplica Mihai Dragos tiriplicamihai Data 5 martie 2010 19:10:15
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.39 kb
#include <fstream.h>
#include <math.h>

struct pct{
	double x,y,cos;}v[120001],s[120001],v1[120001],v2[120001];
	
long n,vf,k,k1,i,a;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");


double dist(double x1,double y1,double x2,double y2)
{
	return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}

double cosinus(pct p,pct p0)
{
	return (p.x-p0.x)/(dist(p0.x,p0.y,p.x,p.y));
}

void cit()
{
	long i,poz;
	double minx=5000,miny=5000;
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>v[i].x>>v[i].y;
		//v[i].cos=cosinus(v[i]);//gresit se calc unghiul cu p0
		if(v[i].y<miny)
		{
			minx=v[i].x;
			miny=v[i].y;
			poz=i;
		}
		if(fabs(v[i].y-miny)<0.000000000001&&v[i].x<minx)
		{
			minx=v[i].x;
			miny=v[i].y;
			poz=i;
		}
	}
	vf++;
	s[vf]=v[poz];
	k=0;
	for(i=1;i<=n;i++)
		if(i!=poz)
		{
			k++;
			v1[k]=v[i];
			v1[k].cos=cosinus(v1[k],v[poz]);
		}
	fin.close();
}


void poz(long li,long ls,long &a)
{
	long i1=0,j1=-1,i=li,j=ls,c1;
	pct c;
	while(i<=j)
	{
		if(v1[i].cos<v1[j].cos)
		{
			c=v1[i];
			v1[i]=v1[j];
			v1[j]=c;
			c1=i1;
			i1=-j1;
			j1=-c1;
		}
		if(fabs(v1[i].cos-v1[j].cos)<0.000000000001)
		{
			if(v1[i].x<v1[j].x)
			{
				c=v1[i];
				v1[i]=v1[j];
				v1[j]=c;
				c1=i1;
				i1=-j1;
				j1=-c1;
			}
			if(fabs(v1[i].x-v1[j].x)<0.000000000001)
			{
				if(v1[i].y>v1[j].y)
				{
					c=v1[i];
					v1[i]=v1[j];
					v1[j]=c;
					c1=i1;
					i1=-j1;
					j1=-c1;
				}
			}
		}
		i+=i1;
		j+=j1;
	}
	a=i;
}

void sort(long li,long ls)
{
	if(li<=ls)
	{
		poz(li,ls,a);
		sort(li,a-1);
		sort(a+1,ls);
	}
}

void elimin()
{
	long i,j;
	double aux;
	k1=0;
	for(i=1;i<=k;i++)
		if(v1[i].cos!=15)
		{
			aux=v1[i].cos;
			j=i+1;
			while(fabs(aux-v1[j].cos)<0.000000000001)
			{
				v1[j-1].cos=15;
				j++;
			}
			k1++;
			v2[k1]=v1[j-1];
			v1[j-1].cos=15;
				
		}
}

double det(pct p1,pct p2,pct  p3)
{
	return((p1.x-p3.x)*(p2.y-p3.y)-(p1.y-p3.y)*(p2.x-p3.x));
}

void infas()
{
	long i;
	double d;
	vf++;
	s[vf]=v2[1];
	vf++;
	s[vf]=v2[2];
	for(i=3;i<=k1;i++)
	{
		d=det(s[vf],s[vf-1],v2[i]);
		while(d>0)
		{
			vf--;
			d=det(s[vf],s[vf-1],v2[i]);
		}
		vf++;
		s[vf]=v2[i];
	}
}

int main()
{
	cit();
	sort(1,k);
	elimin();
	infas();
	fout<<vf<<"\n";
	for(i=1;i<=vf;i++)
		fout<<s[i].x<<" "<<s[i].y<<"\n";
	fout.close();
	return 0;
}