Pagini recente » Cod sursa (job #2824096) | Cod sursa (job #370973) | Cod sursa (job #1681944) | Cod sursa (job #2796779) | Cod sursa (job #1590953)
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#define eps 1e-12
using namespace std;
int n,i,h,k,q;
typedef struct coordonata
{
double x,y;
};
coordonata p[120010],v[120010];
int s[120010],ok[120010];
inline int cmp1(double a,double b)
{
if (a+eps<b) return 1;
if (b+eps<a) return -1;
return 0;
}
bool cmp(const coordonata &a,const coordonata&b)
{
int t;
t=cmp1(a.x,b.x);
if (t!=0) return t==1;
return (cmp1(a.y,b.y)==1);
}
int semn(coordonata a,coordonata b,coordonata c)
{
double A,B,C;
A = a.y-b.y;
B = b.x-a.x;
C = a.x*b.y - b.x*a.y;
return cmp1(A*c.x+B*c.y+C,0);
}
int main ()
{
freopen("infasuratoare.in","r",stdin);
ofstream g ("infasuratoare.out");
scanf("%d",&n);
for (i=1; i<=n; i++)
scanf("%lf%lf",&v[i].x,&v[i].y);
sort(v+1,v+n+1,cmp);
s[1]=1;
s[2]=2;
q=1;
k=2;
i=3;
while (!ok[1])
{
while (ok[i])
{
if (i==n) q=-1;
i+=q;
}
while (k>=2 && semn(v[s[k-1]],v[s[k]],v[i])==-1)
{
ok[s[k--]]=0;
}
s[++k]=i;
ok[i]=1;
}
h=k-1;
g<<h<<'\n';
for (i=2; i<=h+1; i++)
g<<setprecision(6)<<fixed<<v[s[i]].x<<" "<<v[s[i]].y<<'\n';
return 0;
}