Cod sursa(job #392555)

Utilizator roxana1roxana ionescu roxana1 Data 7 februarie 2010 18:44:36
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.22 kb
#include<fstream>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct {float x,y;};
punct s[100],s1[100],s2[100],p1,p2,p3,aux;
int i,n,nr1,nr2,j,imax,imin,ok;

float xmax,xmin;
int cmp(const void *i,const void *j)
{punct *p1=(punct *)i,*p2=(punct *)j;
return(p1->x>p2->x||p1->x==p2->x&&p1->y>p2->y);
}


/*int cmp(const void *i,const void *j)
{
entry *ei = (entry *) i, *ej =
(entry *) j;
if (ei->x != ej->x)
return ei->x - ej->x;
return ej->sgn - ei->sgn;
}
*/


float sarrus(punct *p1,punct *p2,punct *p3)
{float d;
d=p1->x*p2->y+p2->x*p3->y+p1->y*p3->x-p2->y*p3->x-p3->y*p1->x-p2->x*p1->y;
return d;
}
int main()
{f>>n;
for(i=1;i<=n;i++)
	f>>s[i].x>>s[i].y;
xmin=32000;
xmax=-32000;
for(i=1;i<=n;i++)
		{if(s[i].x<xmin)
		{xmin=s[i].x;
		imin=i;
		}
		if(s[i].x>xmax)
		{xmax=s[i].x;
		imax=i;}
		}
nr1=1;
nr2=1;
s1[nr1]=s[imin];
s2[nr2]=s[imin];
for(i=1;i<=n;i++)
	if(i!=imin&&i!=imax)
		if(sarrus(&s[imin],&s[imax],&s[i])<0)
		{nr1++;
		s1[nr1]=s[i];}
		else
		{nr2++;
		s2[nr2]=s[i];
		}
nr1++;
s1[nr1]=s[imax];
nr2++;
s2[nr2]=s[imax];

/*for(i=1;i<=nr1;i++)
	
	g<<s1[i].x<<" "<<s1[i].y<<'\n';
 g<<'\n';
 for(i=1;i<=nr2;i++)
	
	g<<s2[i].x<<" "<<s2[i].y<<'\n';
 g<<'\n';*/
qsort(s1+1,nr1,sizeof(punct),cmp);
qsort(s2+1,nr2,sizeof(punct),cmp);
/*for(i=1;i<nr1;i++)
	for(j=i+1;j<=nr1;j++)
		if(s1[i].x>s1[j].x||s1[i].x==s1[j].x&&s1[i].y>s1[j].y)
		{aux=s1[i];
		s1[i]=s1[j];
		s1[j]=aux;
		}
	for(i=1;i<nr2;i++)
	for(j=i+1;j<=nr2;j++)
		if(s2[i].x>s2[j].x||s2[i].x==s2[j].x&&s2[i].y>s2[j].y)
		{aux=s2[i];
		s2[i]=s2[j];
		s2[j]=aux;
		}	
		*/ 

do
{ok=0;
 i=2;
 while(i<nr1)
 {p1=s1[i-1];
 p2=s1[i];
 p3=s1[i+1];
 if(sarrus(&p1,&p2,&p3)>0)
	 i++;
 else
 {ok=1;
 for(j=i;j<nr1;j++)
	 s1[j]=s1[j+1];
 nr1--;}
 }}
 while(ok);
 do
{ok=0;
 i=2;
 while(i<nr2)
 {p1=s2[i-1];
 p2=s2[i];
 p3=s2[i+1];
 if(sarrus(&p1,&p2,&p3)<0)
	 i++;
 else
 {ok=1;
 for(j=i;j<nr2;j++)
	 s2[j]=s2[j+1];
 nr2--;}
 }}
 while(ok);


 for(i=nr1;i>1;i--)
 {nr2++;
 s2[nr2]=s1[i];
 }
 g.precision(10);
 g<<nr2<<'\n';
 for(i=nr2;i>=1;i--)
	
	g<<s2[i].x<<" "<<s2[i].y<<'\n';
 g<<'\n';
 
 f.close();
 g.close();
 return 0;
}