Pagini recente » runda/suceavaftw | Cod sursa (job #1978222) | Cod sursa (job #1496179) | Cod sursa (job #1923073) | Cod sursa (job #392555)
Cod sursa(job #392555)
#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;
}