Pagini recente » Cod sursa (job #1213136) | Cod sursa (job #3182292) | Cod sursa (job #2924767) | Cod sursa (job #1080406) | Cod sursa (job #1920706)
#include <bits/stdc++.h>
using namespace std;
#define eps 0.000000000001
int st[120005],n,i,nr,ap[120005];
struct punct
{
double x,y;
}a[120005];
double modul(double x)
{
if(x<0)return -x;
return x;
}
bool egal(double x, double y)
{
if(modul(x-y)<=eps)return 1;
return 0;
}
bool cmp(punct a, punct b)
{
if(egal(a.x,b.x))return a.y<b.y;
return a.x<b.x;
}
/**
ax ay 1
bx by 1
cx cy 1
**/
double det(punct A, punct B, punct C)
{
return (double) A.x*B.y+B.x*C.y+A.y*C.x-C.x*B.y-A.y*B.x-A.x*C.y;
}
void elimin(int i)
{
while(nr>=2&&det(a[st[nr-1]],a[st[nr]],a[i])<eps)
{
ap[st[nr]]=0;
nr--;
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
sort(a+1,a+n+1,cmp);
nr=2;
st[1]=1;
st[2]=2;
ap[2]=1;
for(i=3;i<=n;i++)
{
elimin(i);
nr++;
st[nr]=i;
ap[i]=1;
}
for(i=n;i>1;i--)
{
if(ap[i]==0)
{
elimin(i);
nr++;
st[nr]=i;
ap[i]=1;
}
}
elimin(1);
printf("%d\n",nr);
for(i=1;i<=nr;i++)
{
printf("%lf %lf\n",a[st[i]].x,a[st[i]].y);
}
return 0;
}