Cod sursa(job #274398)

Utilizator irene_mFMI Irina Iancu irene_m Data 9 martie 2009 18:05:24
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.09 kb
#include <fstream.h>
#include <iomanip.h>
#include <values.h>
int n,minx=MAXINT,miny,k;
float x[120000],y[120000],xf[120000],yf[120000];

void cit()
{
	int i;
	ifstream fin("infasuratoare.in");
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>x[i]>>y[i];
		if(x[i]<minx)
		{
			minx=x[i]; miny=y[i];
		}
		else
		if(x[i]==minx && y[i]<miny)
			miny=y[i];
	}
	fin.close();
}

void trans()
{
	int i;
	for(i=1;i<=n;i++)
	{
		x[i]-=minx;
		y[i]-=miny;
	}
}

void poz(int li,int ls)
{
	int i,j,ii,jj,c;
	float di,dj;
	ii=0; jj=-1;
	i=li; j=ls;
	while(i<=j)
	{
		if(x[i]==0)
		{
			di=MAXINT;
			if(x[j]==0)
				dj=MAXINT;
			else
				dj=y[j]/x[j];
		}
		else
			if(x[j]==0)
			{
				dj=MAXINT;
				if(x[i]==0)
					di=MAXINT;
				else
					di=y[i]/x[i];
			}
			else
			{
				di=y[i]/x[i];
				dj=y[j]/x[j];
			}
		if(di>dj)
		{
			c=x[i]; x[i]=x[j]; x[j]=c;
			c=y[i]; y[i]=y[j]; y[j]=c;
			c=ii;
			ii=-jj;
			jj=-c;
		}
		else
		if(di==dj)
		{
			di=x[i]*x[i]+y[i]*y[i];
			dj=x[j]*x[j]+y[j]*y[j];
			if(di>dj)
			{
				c=x[i]; x[i]=x[j]; x[j]=c;
				c=y[i]; y[i]=y[j]; y[j]=c;
				c=ii;
				ii=-jj;
				jj=-c;
			}
		}

		i+=ii;
		j+=jj;
	}
	k=i;
}


void quick(int li,int ls)
{
	if(li<ls)
	{
		poz(li,ls);
		quick(li,k-1);
		quick(k+1,ls);
	}
}

void afis()
{
	int i;
	ofstream fout("infasuratoare.out");
	fout<<k+1<<'\n';
	fout.precision(6);
	for(i=1;i<=k+1;i++)
		fout<<setiosflags(ios::showpoint)<<xf[i]+minx<<" "<<yf[i]+miny<<'\n';
	fout.close();
}

int det(int i,int j,int k)
{
	int d,x1,y1,x2,y2,x3,y3;
	x1=xf[i]; y1=yf[i];
	x2=xf[j]; y2=yf[j];
	x3=x[k]; y3=y[k];
	d=x1*y2+x2*y3+x3*y1-x3*y2-x2*y1-x1*y3;
	return d;
}


void parc()
{
	int i,d;
	k=2;
	xf[1]=x[1]; yf[1]=y[1];
	xf[2]=x[2]; yf[2]=y[2];
	for(i=3;i<=n;i++)
	{
		d=det(k-1,k,i);
		while(d<0 && k>1)
		{
			k--;
			d=det(k-1,k,i);
		}
		k++;
		xf[k]=x[i]; yf[k]=y[i];
	}

	d=det(k-1,k,1);
	while(d<0)
	{
		k--;
		d=det(k-1,k,1);
	}
}



int main()
{
	cit();
	trans();
	quick(1,n);
	parc();
	afis();
	return 0;
}