Pagini recente » Cod sursa (job #119644) | Cod sursa (job #2386494) | Cod sursa (job #860194) | Cod sursa (job #1984070) | Cod sursa (job #411078)
Cod sursa(job #411078)
#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[pz].y>a[i].y)
pz=i;
else if(a[pz].y==a[i].y)
if(a[pz].x>a[i].x)
pz=i;
}
}
struct cmp
{
bool operator()(const coord &A,const coord &B) const
{
return (double)(a[1].y-A.y)*(a[1].x-B.x)<(double)(a[1].y-B.y)*(a[1].x-A.x);
}
};
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=1;i<=nr;++i)
printf("%.6lf %.6lf\n",st[i].x,st[i].y);
return 0;
}