Pagini recente » Cod sursa (job #363667) | Cod sursa (job #363665) | Cod sursa (job #368854) | Cod sursa (job #354684) | Cod sursa (job #363666)
Cod sursa(job #363666)
#include <algorithm>
using namespace std;
#define DIM 120005
struct punct {double x,y;} v[DIM];
int st[DIM];
int n,vf;
void swap (punct &a,punct &b)
{
punct aux=a;
a=b;
b=aux;
}
void read ()
{
int i;
scanf ("%d",&n);
for (i=1; i<=n; ++i)
{
scanf ("%lf%lf",&v[i].x,&v[i].y);
if (v[i].x<v[1].x || (v[i].x==v[1].x && v[i].y<v[1].y))
swap (v[1],v[i]);
}
}
int cmp (punct a,punct b)
{
return (a.x-v[1].x)*(b.y-v[1].y)<(b.x-v[1].x)*(a.y-v[1].y);
}
int semn (punct a,punct b,punct c)
{
if (a.x*b.y+b.x*c.y+c.x*a.y>a.y*b.x+b.y*c.x+c.y*a.x)
return 1;
return 0;
}
void solve ()
{
int i;
for (st[++vf]=1, i=2; i<=n; st[++vf]=i++)
for ( ; vf>=2 && semn (v[st[vf-1]],v[st[vf]],v[i])>0; --vf);
}
void print ()
{
int i;
printf ("%d\n",vf);
for (i=vf; i; --i)
printf ("%lf %lf\n",v[st[i]].x,v[st[i]].y);
}
int main ()
{
freopen ("infasuratoare.in","r",stdin);
freopen ("infasuratoare.out","w",stdout);
read ();
sort (v+2,v+n+1,cmp);
solve ();
print ();
return 0;
}