Pagini recente » Cod sursa (job #867157) | Cod sursa (job #1512811) | Cod sursa (job #1605233) | Cod sursa (job #1266508) | Cod sursa (job #1394253)
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
struct str
{
double x;
double y;
double n1;
double n2;
}a[120001];
double comp(str a,str b)
{
return (a.n1*b.n2) < (b.n1*a.n2);
}
double calcarie(double x1,double y1,double x2,double y2,double x3,double y3)
{
double arie=double((double)x1*(y2-y3)+(double)x2*(y3-y1)+(double)x3*(y1-y2));
arie=(double)arie/2;
return arie;
}
int stack[120001];
int pint;
int main()
{
freopen ("infasuratoare.in","r",stdin);
freopen ("infasuratoare.out","w",stdout);
scanf("%d",&n);
double minx=1000000001,miny=1000000001;
int indice;
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&a[i].x,&a[i].y);
if(minx>a[i].x)
{
minx=a[i].x;
miny=a[i].y;
indice=i;
}
else if(minx==a[i].x&&miny>a[i].y)
{
miny=a[i].y;
indice=i;
}
}
for(int i=1;i<indice;i++)
{
a[i].n1=a[i].y-a[indice].y;
a[i].n2=a[i].x-a[indice].x;
}
for(int i=indice+1;i<=n;i++)
{
a[i].n1=a[i].y-a[indice].y;
a[i].n2=a[i].x-a[indice].x;
}
swap(a[1],a[indice]);
sort(a+2,a+n+1,comp);
stack[1]=1;
stack[2]=2;
pint=3;
for(int i=3;i<=n;i++)
{
while(calcarie(a[stack[pint-2]].x,a[stack[pint-2]].y,a[stack[pint-1]].x,a[stack[pint-1]].y,a[i].x,a[i].y)<0) pint--;
stack[pint]=i;
pint++;
}
printf("%d\n",pint-1);
for(int i=1;i<pint;i++)
{
printf("%lf %lf\n",a[stack[i]].x,a[stack[i]].y);
}
}