Pagini recente » Cod sursa (job #99317) | Cod sursa (job #1224258) | Cod sursa (job #2862515) | Cod sursa (job #806326) | Cod sursa (job #1199162)
#include <cstdio>
#include <algorithm>
#define Nmax 120005
#define eps 0.000000000001
using namespace std;
struct pc
{
double x,y;
bool operator <(const pc A) const
{
return y<A.y;
}
};
pc v[Nmax];
int st[Nmax],top;
bool viz[Nmax];
inline double Semn(pc A, pc B, pc C)
{
return -(C.x-A.x)*(B.y-A.y)+(B.x-A.x)*(C.y-A.y);
}
int main()
{
int i,N,sign=1;
freopen ("infasuratoare.in","r",stdin);
freopen ("infasuratoare.out","w",stdout);
scanf("%d", &N);
for(i=1;i<=N;++i)
scanf("%lf%lf", &v[i].x, &v[i].y);
sort(v+1,v+N+1);
st[++top]=1; st[++top]=2; viz[2]=true;
for(i=3;i;i+=sign)
if(!viz[i])
{
while(top>1 && Semn(v[st[top-1]],v[st[top]],v[i])<=eps)
viz[st[top--]]=false;
st[++top]=i; viz[i]=true;
if(i==N)
sign=-1;
}
printf("%d\n", top-1);
for(i=1;i<top;++i)
printf("%.6lf %.6lf\n", v[st[i]].x, v[st[i]].y);
return 0;
}