Pagini recente » Cod sursa (job #2567047) | Cod sursa (job #1672731) | Cod sursa (job #3270045) | Cod sursa (job #3212087) | Cod sursa (job #752241)
Cod sursa(job #752241)
#include <cstdio>
#include <algorithm>
#include <vector>
#define pdd pair <double,double>
#define x first
#define y second
#define NMAX 120005
using namespace std;
int n,k;
vector<pdd> a;
pdd st[NMAX];
pdd aux;
void cit()
{freopen("infasuratoare.in","rt",stdin);
freopen("infasuratoare.out","wt",stdout);
scanf("%d",&n);
a.push_back(aux);
for (register int i=1; i<=n; i++)
{scanf("%lf%lf",&aux.x,&aux.y);
a.push_back(aux);
}
}
inline int semn(pdd a,pdd b,pdd c)
{double A=a.y-b.y; double B=b.x-a.x;
double C=a.x*b.y-b.x*a.y;
return (A*c.x+B*c.y+C)<0;
}
void infas()
{st[++k]=a[1]; st[++k]=a[2];
for (register int i=3; i<=n; i++)
{while (k>=2 && semn(st[k-1],st[k],a[i])) k--;
st[++k]=a[i];
}
for (register int i=n-1; i>=1; i--)
{while (k>=2 && semn(st[k-1],st[k],a[i])) k--;
st[++k]=a[i];
}
//k--;
printf("%d\n",k-1);
for (register int i=2; i<=k; i++)
printf("%lf %lf\n",st[i].x,st[i].y);
}
int main()
{cit();
sort(a.begin(),a.end());
infas();
return 0;
}