Pagini recente » Cod sursa (job #1354631) | Cod sursa (job #2816385) | Cod sursa (job #1374666) | Cod sursa (job #1153192) | Cod sursa (job #411076)
Cod sursa(job #411076)
#include<stdio.h>
#include<algorithm>
#define Nmx 120001
using namespace std;
struct coord
{
double x,y;
};
coord a[Nmx],st[Nmx];
int n,pz,nr;
void citire()
{
scanf("%d",&n);
pz=1;
for(int i=1;i<=n;++i)
{
scanf("%lf %lf",&a[i].x,&a[i].y);
if(a[i].x<a[pz].x)
pz=i;
else if(a[i].x==a[pz].x)
if(a[i].y<a[pz].y)
pz=i;
}
}
struct cmp
{
bool operator()(const coord &A,const coord &B) const
{
return (double)(A.x-a[1].x)*(B.y-a[1].y)<(double)(B.x-a[1].x)*(A.y-a[1].y);
}
};
double semn(double xa,double ya,double xb,double yb,double xc,double yc)
{
return xa*yb+xb*yc+xc*ya-xc*yb-xa*yc-xb*ya;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
citire();
coord aux;
aux=a[pz];
a[pz]=a[1];
a[1]=aux;
sort(a+2,a+n+1,cmp());
st[++nr]=a[1];
for(int i=2;i<=n;++i)
{
while(nr>=2&&semn(st[nr-1].x,st[nr-1].y,st[nr].x,st[nr].y,a[i].x,a[i].y)>0)
--nr;
st[++nr]=a[i];
}
printf("%d\n",nr);
for(int i=nr;i>=1;--i)
printf("%.6lf %.6lf\n",st[i].x,st[i].y);
return 0;
}