Pagini recente » Istoria paginii runda/eusebiu_oji_2008si2009_cls11-12/clasament | Cod sursa (job #2833665) | Statistici Ion Mihai (veverita927) | Cod sursa (job #1563934) | Cod sursa (job #533924)
Cod sursa(job #533924)
#include <cstdio>
#include <algorithm>
using namespace std;
#define nmax 120010
int n, pi, v[nmax], st[nmax];
double x[nmax], y[nmax];
int cmp(int i, int j)
{
return (x[i]-x[pi])*(y[j]-y[pi]) < (x[j]-x[pi])*(y[i]-y[pi]);
}
double semn(int i1, int i2, int i3)
{
return x[i1]*y[i2]+x[i2]*y[i3]+x[i3]*y[i1]-y[i1]*x[i2]-y[i2]*x[i3]-y[i3]*x[i1];
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
int i;
x[0]=y[0]=1<<30;
for (i=1; i<=n; i++)
{
scanf("%lf %lf",&x[i], &y[i]);
if (x[i]<x[pi] || (x[i]==x[pi] && y[i]<y[pi])) pi=i;
}
for (i=1; i<=n; i++)
if (i!=pi)
v[++v[0]]=i;
sort (v+1, v+v[0]+1, cmp);
int h=1;
st[1]=pi;
for (i=1; i<=v[0]; i++)
{
while (h>1 && semn(st[h-1], st[h], v[i])>0) h--;
st[++h]=v[i];
}
printf("%d\n",h);
for (i=h; i>0; i--)
printf("%lf %lf\n",x[st[i]], y[st[i]]);
}