Cod sursa(job #572866)

Utilizator alexapoApostol Alexandru Ionut alexapo Data 5 aprilie 2011 18:12:00
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
# include <fstream.h>
#include<stdio.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct 
{
	float x,y,p;
}v[120005],aux,inceput,w[120005],s[120005];
int n,i,prim,k,ii,vf,fara=0;
void citprime()
{
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i].x>>v[i].y;
}
void punct_inceput()
{
	prim=1;
	for(i=2;i<=n;i++)
		if(v[i].x<v[prim].x||v[i].x==v[prim].x&&v[i].y<v[prim].y)
			prim=i;
}
void pante()
{
	for(i=1;i<=n;i++)
		if(i!=prim)
			if(v[i].x==v[prim].x)
			{
				if(ii==0||ii>0&&v[ii].y<v[i].y)
					ii=i;
			}
			else
			{
				v[i].p=(v[i].y-v[prim].y)/(v[i].x-v[prim].x);
				k++;
				w[k]=v[i];
			}
			
}
void ordonare()
{
	int i,j;
	
		for(int i=1;i<k;i++)
			for(j=i;j<=k;j++)
			if(w[i].p>w[j].p||w[i].p==w[j].p&&w[i].x>w[j].x)
			{
				aux=w[i];
				w[i]=w[j];
				w[j]=aux;
			}

}
int elimina(punct a,punct b,punct c)
{
	if(a.x==b.x&&a.x==c.x)
		return 0;
	if((b.y-a.y)*(c.x-a.x)-(c.y-a.y)*(b.x-a.x)<0)
		return 1;
	return 0;
}
void stiva()
{
	s[1]=v[prim];
	s[2]=w[1];
	vf=2;
	for(i=1;i<=k;i++)
	{
		while(elimina(s[vf],s[vf-1],w[i]))
			vf--;
		vf++;
		s[vf]=w[i];
	}
}
void afis()
{
	if(ii>0)g<<vf+1-fara<<'\n';
	else g<<vf-fara<<'\n';
	for(i=1;i<vf;i++)
		if(s[i].x!=s[i+1].x||s[i].y!=s[i+1].y)
		g<<s[i].x<<".000000 "<<s[i].y<<".000000"<<'\n';
	if(ii>0)
		g<<v[ii].x<<".000000 "<<v[ii].y<<".000000"<<'\n';
	g<<s[vf].x<<".000000 "<<s[vf].y<<".000000"<<'\n';
}
void verifica()
{

	for(i=1;i<vf;i++)
		if(s[i].x==s[i+1].x&&s[i].y==s[i+1].y)
			fara++;
}
int main()
{
	citprime();
	punct_inceput();
	pante();
	ordonare();
	stiva();
	verifica();
	afis();
	
	f.close();
	g.close();
	return 0;
}