Pagini recente » Cod sursa (job #1866136) | Cod sursa (job #2849220) | Cod sursa (job #1349381) | Cod sursa (job #2953205) | Cod sursa (job #1686205)
#include <stdio.h>
#include <algorithm>
#define eps 1e-12
#define nmax 120010
using namespace std;
struct date { double x,y; };
int n,head;
int stiva[nmax];
bool fr[nmax];
date t[nmax];
inline double abss(double x) { if (x<eps) return (-x); else return x; }
bool cmp(const date &a,const date &b)
{
if (abss(a.x-b.x)<=eps) return ((a.y-b.y)<=eps); else
return ((a.x-b.x)<=eps);
}
double upperline(date a,date b,date c)
{
return a.x*b.y+a.y*c.x+b.x*c.y-b.y*c.x-c.y*a.x-a.y*b.x;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%lf %lf",&t[i].x,&t[i].y);
sort(t+1,t+n+1,cmp);
head=2; stiva[1]=1; stiva[2]=2; fr[2]=true;
for (int i=3;i<=n;i++) {
if (fr[i]) continue;
while (head>=2 && upperline(t[stiva[head-1]],t[stiva[head]],t[i])>eps) fr[stiva[head]]=false,head--;
head++; stiva[head]=i; fr[i]=true;
}
for (int i=n;i>=1;i--) {
if (fr[i]) continue;
while (head>=2 && upperline(t[stiva[head-1]],t[stiva[head]],t[i])>eps) fr[stiva[head]]=false,head--;
head++; stiva[head]=i; fr[i]=true;
}
printf("%d\n",head-1);
for (int i=head-1;i>=1;i--) printf("%f %f\n",t[stiva[i]].x,t[stiva[i]].y);
return 0;
}