Pagini recente » Cod sursa (job #2778991) | Cod sursa (job #853075) | Cod sursa (job #1845651) | Cod sursa (job #191522) | Cod sursa (job #1826715)
#include <cstdio>
#include <algorithm>
using namespace std;
const double eps=1e-12;
#define x first
#define y second
typedef pair<double,double> POINT;
int n;
POINT v[120005];
bool viz[120005];
int st[120005],top;
double cross_product(POINT P1,POINT P2,POINT P3)
{
return (P2.x-P1.x)*(P3.y-P1.y)-(P2.y-P1.y)*(P3.x-P1.x);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int i,p;
scanf("%d",&n);
for(i=1; i<=n; i++)
scanf("%lf%lf",&v[i].x,&v[i].y);
sort(v+1,v+n+1);
st[++top]=1;
st[++top]=2;
viz[2]=1;
for(i=1, p=1; i>0; i+=(p=(i==n?-p:p)))
if(!viz[i])
{
while(top>=2 && cross_product(v[st[top-1]],v[st[top]],v[i])<eps)
viz[st[top--]]=0;
st[++top]=i;
viz[i]=1;
}
top--;
printf("%d\n",top);
for(i=1; i<=top; i++)
printf("%.6f %.6f\n",v[st[i]].x,v[st[i]].y);
return 0;
}