Pagini recente » Cod sursa (job #3187146) | Cod sursa (job #264644) | Cod sursa (job #899506) | Cod sursa (job #314333) | Cod sursa (job #1395878)
#include <stdio.h>
#include <algorithm>
#define inf 1000000000
using namespace std;
int n,i,s[120001],u,j;
double ym,xm;
struct punct
{
double x,y;
}p[120001];
double det(punct o,punct a,punct b)
{
return ((a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x));
}
double dist(punct a,punct b)
{
return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool sortare(punct a,punct b)
{
double r=det(p[1],a,b);
return (r>0||(r==0&&dist(p[1],a)<dist(p[1],b)));
}
void solve()
{
int i;
double r;
u=2; s[1]=1; s[2]=2;
for (i=3;i<=n;i++)
{
r=det(p[s[u-1]],p[s[u]],p[i]);
if (r>0) s[++u]=i;
else if (r==0) s[u]=i;
else
{
while (r<0)
{
u--;
r=det(p[s[u-1]],p[s[u]],p[i]);
}
s[++u]=i;
}
}
}
int main()
{
freopen ("infasuratoare.in","r",stdin);
freopen ("infasuratoare.out","w",stdout);
scanf("%i",&n);
ym=xm=inf;
for (i=1;i<=n;i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
if (p[i].y<ym||(p[i].y==ym&&p[i].x<xm))
{
ym=p[i].y; xm=p[i].x;
j=i;
}
}
swap(p[j],p[1]);
sort(p+2,p+n+1,sortare);
solve();
printf("%i\n",u);
for (i=1;i<=u;i++)
printf("%f %f\n",p[s[i]].x,p[s[i]].y);
fclose(stdin);
fclose(stdout);
return 0;
}