Pagini recente » 7953532771521155 | Cod sursa (job #535228) | Cod sursa (job #2333452) | Cod sursa (job #2752710) | Cod sursa (job #404999)
Cod sursa(job #404999)
#include<stdio.h>
#include<deque>
#include<algorithm>
using namespace std;
#define inf 1000000001
#define NMAX 120000
double PX=inf,PY=inf;
int ind=-1;
double X[NMAX],Y[NMAX];
int I[NMAX],D[NMAX];
inline bool cmp( int p1, int p2 )
{
return (double)( X[p1]-PX )*( Y[p2]-PY )<(double)( Y[p1]-PY )*( X[p2]-PX );
}
inline bool semn( int p1, int p2, int p3 )
{
return (double)( X[p1]-X[p3] )*( Y[p2]-Y[p3] )<(double)( Y[p1]-Y[p3] )*( X[p2]-X[p3] );
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int N;
scanf("%d",&N);
int i;
double a1,a2;
for( i=1; i<=N; ++i )
{
scanf("%lf %lf",&a1,&a2);
X[i]=a1,Y[i]=a2;
if( PX>a1 || ( PX==a1 && PY>a2 ) )
{
PX=a1, PY=a2, ind=i;
}
}
for(i=1; i<=N; ++i)
{
if( i==ind ) continue;
else
I[ ++I[0] ]=i;
}
sort( I+1, I+I[0]+1, cmp );
int sf=1;
D[sf]=ind;
for(i=1; i<=I[0]; ++i)
{
while( sf>=2 && !semn( D[sf-1], D[sf], I[i] ) ) --sf;
D[++sf]=I[i];
}
printf("%d\n",sf);
for(i=sf; i>0; --i)
{
printf("%lf %lf\n",X[ D[i] ], Y[ D[i] ]);
}
return 0;
}