Cod sursa(job #572015)

Utilizator alexapoApostol Alexandru Ionut alexapo Data 4 aprilie 2011 22:15:24
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 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[100],aux,inceput,w[100],s[100];
int n,i,prim,k,ii,vf;
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 o,t=k;
	do{
		o=1;
		for(int i=1;i<t;i++)
			if(w[i].p>w[i+1].p||w[i].p==w[i+1].p&&w[i].x>w[i+1].x)
			{
				aux=w[i];
				w[i]=w[i+1];
				w[i+1]=aux;
			}
			t--;
	}while(!o);
}
int elimina(punct a,punct b,punct c)
{
	if(a.x==b.x&&a.x==c.x)
		return 1;
	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()
{
	for(i=1;i<=vf;i++)
		g<<s[i].x<<".000000 "<<s[i].y<<".000000"<<'\n';
	if(ii>0)
		g<<v[ii].x<<".000000 "<<v[ii].y<<".000000"<<'\n';
}
int main()
{
	citprime();
	punct_inceput();
	pante();
	ordonare();
	stiva();
	afis();
	f.close();
	g.close();
	return 0;
}