Pagini recente » Cod sursa (job #2035551) | Cod sursa (job #953021) | Cod sursa (job #969691) | Cod sursa (job #2607480) | Cod sursa (job #360484)
Cod sursa(job #360484)
#include<cstdio>
#include<algorithm>
#include<math.h>
using namespace std;
#define N 120001
int n,ind[N],st[N],p;
double x[N],y[N];
bool compar(const int&a,const int&b)
{
return (double)(x[a]-x[p])*(y[b]-y[p])<(double)(x[b]-x[p])*(y[a]-y[p]);
}
void citire()
{
scanf("%d",&n);
scanf("%lf%lf",&x[1],&y[1]);
p=1;
for(int i=2; i<=n; ++i)
{
scanf("%lf%lf",&x[i],&y[i]);
if(x[i]<x[p]||(x[i]==x[p]&&y[i]<y[p]))
p=i;
}
for(int i=1; i<=n; ++i)
{
if(i==p)
continue;
ind[++ind[0]]=i;
}
}
double sens(int a,int b,int c)
{
return (double)x[a]*y[b]+x[b]*y[c]+x[c]*y[a]-y[a]*x[b]-y[b]*x[c]-y[c]*x[a];
}
void infasuratoare()
{
st[++st[0]]=p;
for (int i=1; i<n; ++i)
{
//if (ind[i]==p)continue;
while (st[0]-1&&sens(st[st[0]-1],st[st[0]],ind[i])>0)
--st[0];
st[++st[0]]=ind[i];
}
}
void afis()
{
printf("%d\n",st[0]);
reverse(st+1,st+1+st[0]);
for (int i=1; i<=st[0]; ++i)
printf("%lf %lf\n",x[st[i]],y[st[i]]);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
citire();
sort(ind+1,ind+1+ind[0],compar);
infasuratoare();
afis();
return 0;
}