Pagini recente » Cod sursa (job #2055345) | Rating Budea Patrick (MeniuCrunchy) | Cod sursa (job #1610463) | Cod sursa (job #2982290) | Cod sursa (job #1525924)
#include<cstdio>
#include<algorithm>
#define EPS 0.0000000000001
using namespace std;
int st[120007],ap[120007],n,i,nr;
struct punct
{
double x,y;
}pct[120007];
int modul(double x, double y)
{
if(x<y) return y-x;
else return x-y;
}
bool egal(double x, double y)
{
return modul(x,y)<=EPS;
}
int cmp(punct m, punct n)
{
if(egal(m.x,n.x)) return m.y<n.y;
return m.y<n.y;
}
//A.x A.y 1;
//B.x B.y 1;
//C.x C.y 1;
//A.x A.y 1;
//B.x B.y 1;
int det(punct A, punct B, punct C)
{
return (double)A.x*B.y+B.x*C.y+C.x*A.y-C.x*B.y-A.x*C.y-B.x*A.y;
}
void elimin(int i)
{
while(nr>=2&&det(pct[st[nr-1]],pct[st[nr]],pct[i])<EPS)
{
ap[st[nr]]=0;
nr--;
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lf %lf",&pct[i].x,&pct[i].y);
sort(pct+1,pct+n+1,cmp);
st[1]=1;
st[2]=2;
ap[2]=1;
nr=2;
for(i=3;i<=n;i++)
{
elimin(i);
nr++;
st[nr]=i;
ap[i]=1;
}
for(i=n;i>=1;i--)
{
if(ap[i]==0)
{
elimin(i);
nr++;
st[nr]=i;
ap[i]=1;
}
}
elimin(1);
printf("%d\n",nr);
for(i=1;i<=nr;i++)
printf("%.6lf %.6lf\n",pct[st[i]].x,pct[st[i]].y);
return 0;
}