Pagini recente » Cod sursa (job #548155) | Cod sursa (job #2633201) | Cod sursa (job #22776) | Cod sursa (job #919903) | Cod sursa (job #266400)
Cod sursa(job #266400)
#include<fstream.h>
#include<math.h>
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct pcte
{float x,y;
};
pcte p[100],auux,a,b,c;
float i,j,n,vf,s[120001],prod,u1,u2;
float produs(int i,int j, int k)
{
float z1=0,z2=0;
z1=p[i].x*p[j].y + p[i].y*p[k].x + p[j].x*p[k].y;
z2=p[j].y*p[k].x + p[i].y*p[j].x + p[k].y*p[i].x;
return z1-z2;
}
int main(void)
{
f>>n;
for(i=1;i<=n;i++)
f>>p[i].x>>p[i].y;
for(i=1;i<=n;i++)
if(p[1].y>p[i].y||p[i].y==p[i].y&&p[1].x>p[i].x)
{
auux=p[1];
p[1]=p[i];
p[i]=auux;
}
for(i=2;i<=n-1;i++)
for(j=i+1;j<=n;j++)
{
u1=atan2((p[i].x-p[1].x),(p[i].y-p[1].y));
u2=atan2((p[j].x-p[1].x),(p[j].y-p[1].y));
if(u1<0)
u1=u1+2*M_PI;
if(u2<0)
u2=u2+2*M_PI;
if(u1>u2)
{
auux=p[i];
p[i]=p[j];
p[j]=auux;
}
}
s[1]=1;
s[2]=2;
vf=2;
for(i=3;i<=n;i++)
{
prod=produs(s[vf-1],s[vf],i);
if(prod==0)
s[vf]=i;
else
if(prod<0)
{
vf++;
s[vf]=i;
}
else
{
while(prod>0&&vf>2)
{
vf--;
prod=produs(s[vf-1],s[vf],i);
}
vf++;
s[vf]=i;
}
}
g<<vf<<'\n';
g.precision(6);
for(i=vf;i>=1;i--)
g<<p[s[i]].x<<" "<<p[s[i]].y<<'\n';
return 0;
}