Cod sursa(job #410260)

Utilizator tiriplicamihaiTiriplica Mihai Dragos tiriplicamihai Data 4 martie 2010 11:04:28
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include <fstream.h>
#include <math.h>

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

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


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

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

void cit()
{
	int 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.0001&&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(int li,int ls,int &a)
{
	int 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;
		}
		i+=i1;
		j+=j1;
	}
	a=i;
}

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

void elimin()
{
	int i,j;
	k1=0;
	for(i=1;i<=k;i++)
		if(v1[i].cos!=101)
		{
			k1++;
			v2[k1]=v1[i];
			for(j=i+1;j<=k;j++)
				if(fabs(v1[i].cos-v1[j].cos)<0.0001)
					v1[j].cos=101;
				else
					break;
		}
}

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()
{
	int 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;
}