Pagini recente » Cod sursa (job #185646) | Cod sursa (job #2398796) | Cod sursa (job #1491225) | Cod sursa (job #891637) | Cod sursa (job #1627373)
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
int n,q,nr=2,s[120001];
struct punct
{
float x,y,tg;
} a[120001];
void cit()
{
scanf("%d ",&n);
int i;
for(i=1; i<=n; ++i)
scanf("%f %f ",&a[i].x,&a[i].y);
}
void afis()
{
printf("%d\n",nr);
int i;
for(i=1; i<=nr; ++i)
printf("%f %f\n",a[s[i]].x,a[s[i]].y);
}
void aleg()
{
int i;
float miny=1000000000,minx=1000000000;
for(i=1; i<=n; ++i)
{
if(miny>a[i].y)
{
miny=a[i].y;
minx=a[i].x;
q=i;
}
else if(miny==a[i].y&&minx>a[i].x)
{
minx=a[i].x;
q=i;
}
}
}
inline bool comp(punct i, punct j)
{
if(i.tg<0&&j.tg>=0) return 0;
if(i.tg>=0&&j.tg<0) return 1;
if(i.tg!=j.tg) return(i.tg<j.tg);
else return (sqrt((i.y-a[q].y)*(i.y-a[q].y)+(i.x-a[q].x)*(i.x-a[q].x))<sqrt((j.y-a[q].y)*(j.y-a[q].y)+(j.x-a[q].x)*(j.x-a[q].x)));
}
void tang()
{
int i;
for(i=1; i<=n; ++i)
a[i].tg=(a[i].y-a[q].y)/(a[i].x-a[q].x);
sort(a+1,a+n+1,comp);
}
inline bool ok(int p0, int p1, int p2)
{
return(((a[p1].x-a[p0].x)*(a[p2].y-a[p0].y)-(a[p2].x-a[p0].x)*(a[p1].y-a[p0].y))>=0);
}
void generare()
{
int i,p1=1,p2=2,p=1;
for(i=3; i<=n; ++i)
{
if(ok(p1,p2,i))
{
++nr;
p=p1;
p1=p2;
p2=i;
s[nr]=i;
}
else
{
p2=p1;
p1=p;
--i;
--nr;
}
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
cit();
aleg();
tang();
s[1]=1;
s[2]=2;
generare();
afis();
return 0;
}