Pagini recente » Cod sursa (job #1225707) | Cod sursa (job #1942103) | Cod sursa (job #1096771) | Cod sursa (job #696047) | Cod sursa (job #1435440)
#include <cstdio>
#include <algorithm>
#define eps 1e-12
using namespace std;
struct punct
{
double x;
double y;
};
punct a[120001];
int comp(double a, double b)
{
if (a+eps<b) return 1;
if (b+eps<a) return -1;
return 0;
}
bool cmp(punct a, punct b)
{
int t;
t=comp(a.x,b.x);
if (t!=0)
{
if (t==1) return true;
else return false;
}
else return (comp(a.y,b.y)==1);
}
bool determinant(punct a, punct b, punct c)
{
double det=a.x * b.y + c.x * a.y + b.x * c.y - c.x * b.y - b.x * a.y - a.x * c.y;
return (comp(det,0)==1);
}
int st[120001],n,i,nr1,q;
bool ok[120001];
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d\n",&n);
for (i=1; i<=n; i++) scanf("%lf %lf\n",&a[i].x,&a[i].y);
sort(a+1,a+n+1,cmp);
st[1]=1;
st[0]=2;
st[2]=2;
ok[2]=true;
q=1;
i=3;
while (!ok[1])
{
while (ok[i])
{
if (i==n) q=-1;
i+=q;
}
while (st[0]>=2 && !determinant(a[st[st[0]]],a[st[st[0]-1]],a[i])) ok[st[st[0]--]]=false;
st[++st[0]]=i;
ok[st[st[0]]]=true;
}
nr1=st[0]-1;
printf("%d\n",nr1);
for (i=2; i<=nr1+1; i++) printf("%lf %lf\n",a[st[i]].x,a[st[i]].y);
return 0;
}