Pagini recente » Cod sursa (job #1875414) | Cod sursa (job #1537995) | Cod sursa (job #132375) | Cod sursa (job #1399262) | Cod sursa (job #266045)
Cod sursa(job #266045)
#include<fstream.h>
#include<math.h>
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct { double x,y;
} a[1000];
int n,u=1,s[10000];
double min=3200000,min1=3200000;
int sgn(punct b,punct c,punct d)
{
double semn=((b.x-d.x)*(c.y-d.y)-(b.y-d.y)*(c.x-d.x));
if(semn>0) return 1;
if(semn<0) return -1;
return 0;
}
void sort(int x,int y)
{ int i=x,j=y;
punct p=a[(i+j)/2],aux;
do {
while(sgn(a[1],a[i],p)==1) ++i;
while(sgn(a[1],p,a[j])==1) --j;
if(i<=j) { aux=a[i];
a[i]=a[j];
a[j]=aux;
++i;
--j;
}
} while(i<=j);
if(x<j) sort(x,j);
if(i<y) sort(i,y);
}
int main()
{ int i;
fin>>n;
for(i=1;i<=n;i++)
{ fin>>a[i].x>>a[i].y;
if(a[i].y<min){ min=a[i].y;
min1=a[i].x;
a[0]=a[i];
a[i]=a[1];
a[1]=a[0];
}
else if(a[i].y==min&&a[i].x<min1)
{ min1=a[i].x;
a[0]=a[i];
a[i]=a[1];
a[1]=a[0];
}
}
sort(2,n);
s[u]=1;
for(i=2;i<=n;i++)
{ while(u>1&&sgn(a[s[u-1]],a[s[u]],a[i])==-1)
u--;
s[++u]=i;
}
fout<<u<<"\n";
for(i=1;i<=u;i++)
fout<<a[s[i]].x<<" "<<a[s[i]].y<<"\n";
fin.close();
fout.close();
return 0;
}