Pagini recente » Cod sursa (job #3213919) | Cod sursa (job #669612) | Cod sursa (job #3208210) | Cod sursa (job #2135929) | Cod sursa (job #1349748)
#include<stdio.h>
#include<vector>
#include<algorithm>
#define eps 1e-12
#define N 120003
#define x first
#define y second
using namespace std;
typedef pair<double,double> point;
point v[N];
int st[N],i,k,n,f[N];
double cp(point a, point b,point c)
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
bool cmp (point a, point b)
{
if(a.y==b.y)
return a.x<b.x;
return a.y<b.y;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lf%lf",&v[i].x,&v[i].y);
sort(v+1,v+1+n,cmp);
st[1]=1;
st[2]=2;
k=2;
for(i=3;i<=n;i++)
{
while(k>=2&&cp(v[st[k-1]],v[st[k]],v[i])<=eps)
k--;
k++;
st[k]=i;
}
for(i=1;i<=k;i++)
f[st[i]]=1;
f[1]=0;
for(i=n;i>=1;i--)
{
if(f[i]==1)
continue;
while(k>=2&&cp(v[st[k-1]],v[st[k]],v[i])<=eps)
k--;
k++;
st[k]=i;
}
printf("%d\n",k-1);
for(i=1;i<k;i++)
printf("%.6lf %.6lf\n",v[st[i]].x,v[st[i]].y);
return 0;
}