Pagini recente » Cod sursa (job #995013) | Cod sursa (job #2268453) | Cod sursa (job #1698407) | Cod sursa (job #1448373) | Cod sursa (job #1128794)
#include <stdio.h>
#include<algorithm>
using namespace std;
struct Punct{double x,y;};
Punct p[120005],s[120005];
int n,varf;
void cit()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int i;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
}
inline double produs(const Punct& A,const Punct& B,const Punct& C)
{
return (B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x);
}
inline int cmp(const Punct& p1, const Punct& p2)
{
return produs(p[1],p1,p2)<0;
}
void swap(int i, int j)
{
Punct aux;
aux=p[i];
p[i]=p[j];
p[j]=aux;
}
void sortp()
{
int i,k=1;
for(i=2;i<=n;i++)
if(p[k].x>p[i].x)
k=i;
else
if(p[k].x==p[i].x)
if(p[k].y>p[i].y)
k=i;
swap(1,k);
sort(p+2,p+n+1,cmp);
}
void infasuratoare()
{
sortp();
s[1]=p[1];
s[2]=p[2];
varf=2;
for(int i=3;i<=n;i++)
{
while(varf>1 && produs(s[varf-1],s[varf],p[i])>0)
--varf;
s[++varf]=p[i];
}
}
void afis()
{
printf("%d\n",varf);
for(int i=varf;i>=1;i--)
printf("%.9lf %.9lf\n",s[i].x,s[i].y);
}
int main()
{
cit();
infasuratoare();
afis();
return 0;
}