Pagini recente » Cod sursa (job #1184177) | Cod sursa (job #2454353) | Cod sursa (job #245122) | Cod sursa (job #727992) | Cod sursa (job #559791)
Cod sursa(job #559791)
#include<cstdio>
#include<algorithm>
#define Nmx 120001
#define INF 10000001.0
using namespace std;
int n,pct=1,nr;
struct dat
{
double x,y,panta;
};
dat a[Nmx],st[Nmx];
struct cmp
{
bool operator ()(const dat &A,const dat &B)
{
if(A.panta==B.panta)
if(A.x==B.x)
return A.y<B.y;
else return A.x<B.x;
else return A.panta<B.panta;
}
};
void citire()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%lf%lf",&a[i].x,&a[i].y);
if(a[i].x<a[pct].x)
pct=i;
else if(a[i].x==a[pct].x&&a[i].y<a[pct].y)
pct=i;
}
}
double pnt(double x1,double y1,double x2,double y2)
{
if(x2-x1==0)
return INF;
return (y2-y1)/(x2-x1);
}
void calc()
{
for(int i=1;i<=n;++i)
{
a[i].panta=-INF;
if(pct!=i)
a[i].panta=pnt(a[pct].x,a[pct].y,a[i].x,a[i].y);
}
sort(a+1,a+n+1,cmp());
}
double semn(double x1,double y1,double x2,double y2,double x3,double y3)
{
return x1*y2+x2*y3+x3*y1-x3*y2-x1*y3-x2*y1;
}
void infasuratoare()
{
nr=1;
st[1]=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);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
citire();
calc();
infasuratoare();
return 0;
}