Pagini recente » Cod sursa (job #1137441) | Cod sursa (job #404114) | Cod sursa (job #2175728) | Cod sursa (job #995120) | Cod sursa (job #810329)
Cod sursa(job #810329)
#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 120000
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 = 1;
int i = 2 ;
p = 1 ;
st[ 0 ] = 0;
st[ 1 ] = 1;
viz[ 1 ] = 1;
while( !viz[ 0 ] )
{
while(viz [ i ] )
{
if( i == (n-1) ) p = -1 ;
i += p;
}
while( k >= 1 && semn( pct [ st [ k-1 ] ] , pct[ st [ k ] ] , pct[ i ] ) == -1 )
viz[ st[ k-- ]] = 0;
viz[ i ] = 1 ;
st[ ++k ] = i ;
}
}
void afisare()
{
printf("%d\n",k);
for(int i = k ; i > 0 ; --i )
{
printf("%lf %lf\n" , pct[ st[i] ].f,pct[ st[i] ].s );
}
}
int main()
{
freopen("infasuratoarea.in","r",stdin);
freopen("infasuratoarea.out","w",stdout);
citeste();
sort(pct.begin() , pct.end(),cmp);
infasuratoarea();
afisare();
return 0;
}