Pagini recente » Cod sursa (job #2465795) | Cod sursa (job #1392671) | Cod sursa (job #2159516) | Cod sursa (job #1688632) | Cod sursa (job #810401)
Cod sursa(job #810401)
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std ;
#define PDD pair<double , double >
#define f first
#define s second
#define mk make_pair
#define NMAX 120005
vector< PDD > pct ;
int n ,p , k ,viz[NMAX]={0},st[NMAX];
double x , y ;
int semn( PDD a, PDD b, PDD c )
{
double cx = b.s-a.s ;
double cy = a.f-b.f ;
double cz = b.first * a.second - a.first * b.second ;
if( cx*c.f + cy*c.s+cz < 0 ) return -1 ;
else return 1 ;
}
inline int cmp(PDD a , PDD b )
{
if( a.f < b.f) return 1 ;
else
if( a.f > b.f) return 0 ;
else
if(a.s <= b.s) return 1 ;
else return 0;
}
void citeste()
{
scanf("%d",&n);
for ( int i = 1; i <= n ; ++i )
{
scanf("%lf",&x);
scanf("%lf",&y);
pct.push_back ( mk ( x , y ) );
}
}
void infasuratoarea()
{
k = 2;
int i = 3 ;
p = 1 ;
st[ 1 ] = 1;
st[ 2 ] = 2;
viz[ 2 ] = 1;
while( !viz[ 1 ] )
{
while(viz [ i ] )
{
if( i == n ) p = -1 ;
i += p;
}
while( k >= 2 && semn( pct [ st [ k-1 ]-1 ] , pct[ st [ k ]-1 ] , pct[ i -1 ] ) == -1 )
viz[ st[ k-- ] ] = 0;
viz[ i ] = 1 ;
st[ ++k ] = i ;
}
}
void afisare()
{
printf("%d\n",k-1);
for(int i = k ; i >1 ; --i )
{
printf("%lf %lf\n" , pct[ st[ i ]-1 ].f , pct[ st[ i ]-1 ].s );
}
}
int main()
{
freopen("infasuratoarea.in","r",stdin);
freopen("infasuratoarea.out","w",stdout);
citeste();
sort(pct.begin() , pct.end(),cmp);
infasuratoarea();
afisare();
return 0;
}