Pagini recente » Cod sursa (job #2587980) | Cod sursa (job #2902777) | Cod sursa (job #2821177) | Cod sursa (job #2106442) | Cod sursa (job #1164123)
#include<cstdio>
#include<algorithm>
#define point pair<double,double>
#define x first
#define y second
using namespace std;
const int nmax = 120005;
int n,i,m,st[nmax],top;
point p[nmax];
double cp(point a,point b,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;
}
struct cmp
{
bool operator () (point a,point b) const
{
return cp(p[1],a,b)>0;
}
};
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n); m=1;
for(i=1;i<=n;i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
if(p[i]<p[m]) m=i;
}
swap(p[1],p[m]);
sort(p+2,p+n+1,cmp());
for(i=1;i<=n;i++)
{
while(top>=2 && cp(p[i],p[st[top]],p[st[top-1]])>0) top--;
st[++top]=i;
}
printf("%d\n",top);
for(i=1;i<=top;i++) printf("%lf %lf\n",p[st[i]].x,p[st[i]].y);
return 0;
}