Pagini recente » Cod sursa (job #65066) | Cod sursa (job #2455607) | Cod sursa (job #334986) | Cod sursa (job #1130060) | Cod sursa (job #1125481)
#include<cstdio>
#include<algorithm>
#define x first
#define y second
#define point pair<double,double>
using namespace std;
const int nmax = 120005;
int n,i,aux,st[nmax],m;
point p[nmax];
double cp(const point &a,const point &b,const point &c)
{
return a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x;
}
bool cmp(const point &a,const point &b)
{
return cp(p[1],a,b)<0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n); aux=1;
for(i=1;i<=n;i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
if(p[i]<p[aux]) aux=i;
}
swap(p[1],p[aux]);
sort(p+2,p+n+1,cmp);
for(i=1;i<=n;i++)
{
while(m>=2 && cp(p[st[m-1]],p[st[m]],p[i])>0) m--;
st[++m]=i;
}
printf("%d\n",m);
for(i=m;i;i--) printf("%lf %lf\n",p[st[i]].x,p[st[i]].y);
return 0;
}