Pagini recente » Cod sursa (job #324386) | Cod sursa (job #2813590) | Cod sursa (job #1672613) | Cod sursa (job #2843121) | Cod sursa (job #672772)
Cod sursa(job #672772)
# include <cstdio>
# include <algorithm>
# include <fstream>
# define dim 120005
# define INF 999999999
using namespace std;
ifstream f("infasuratoare.in");
int i , n , k , s[ dim ] , poz;
struct punct
{
double x ,y,panta;
};
punct v[ dim ], o , aux;
inline int cmp ( punct a, punct b)
{
if ( a.panta == b.panta )
return a.x < b.x ;
return a.panta < b.panta;
}
int convex()
{
punct a ,b , c;
double S;
a = v[ s[ k - 1 ] ];
b = v[ s[ k ] ];
c = v[ i ];
S = ( a.x - c.x ) * ( b.y - a.y ) + ( a.x - b.x ) * ( a.y - c.y ) ;
if ( S > 0 )
return 1;
return 0;
}
inline void citire()
{
f >> n;
o.x = o.y = INF ;
for ( i = 1 ; i <= n ; i++ )
{
f >> v[ i ].x >> v[ i ].y;
if ( v[ i ].x < o.x || v[ i ].x == o.x && v[ i ].y < o.y )
o = v[ i ],poz = i;
}
}
inline void rezolva()
{
aux = v[ 1 ];
v[ 1 ] = v[ poz ];
v[ poz ] = aux;
for( i = 2 ; i <= n ; i++ )
v[ i ].panta = ( v[ i ].y - o.y ) / ( v[ i ].x - o.x );
sort( v + 2 , v + n + 1 , cmp );
s[ 1 ] = 1 ;
s[ 2 ] = 2 ;
k = 2 ;
for( i = 3 ; i <= n ; i++ )
{
while ( convex() == 0 && k > 2 )
k--;
k++;
s[ k ] = i;
}
}
inline void afisare()
{
freopen("infasuratoare.out","w",stdout);
int i;
printf("%d\n",k);
for( i = 1 ; i <= k ; i++ )
printf("%0.7lf %0.7lf\n",v[ s[ i ] ].x ,v[ s[ i ] ].y );
}
int main()
{
citire();
rezolva();
afisare();
return 0;
}