Pagini recente » Cod sursa (job #2503556) | Cod sursa (job #227732) | Cod sursa (job #1801928) | Cod sursa (job #1260878) | Cod sursa (job #883434)
Cod sursa(job #883434)
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 120001;
#define x first
#define y second
pair<double,double> V[N];
vector<int> S;
int ind,n;
void READ ()
{
ifstream in ("infasuratoare.in");
in>>n;
in>>V[0].x>>V[0].y;
for( int i=1 ; i < n ; ++i )
{
in>>V[i].x>>V[i].y;
if( V[i] < V[ind] )
ind=i;
}
}
bool CMP (const pair<double,double>& A, const pair<double,double>& B)
{
return ( (A.x-V[0].x)*(B.y-V[0].y) < (B.x-V[0].x)*(A.y-V[0].y) );
}
bool ok (int i,int j,int k)
{
return ( ( (V[j].x-V[i].x)*(V[k].y-V[i].y) - (V[j].y-V[i].y)*(V[k].x-V[i].x) ) > 0 ) ;
}
void SOLVE ()
{
swap ( V[0] , V[ind] );
sort ( V+1 , V+n , CMP );
S.push_back( 0 );
S.push_back( 1 );
for( int i=2 ; i < n ; ++i )
{
for( ; S.size() > 2 && ok( S[S.size()-2] , S[S.size()-1] , i ) ; S.pop_back() );
S.push_back( i );
}
}
void OUT ()
{
freopen ("infasuratoare.out","w",stdout);
printf("%d\n",S.size());
for( vector<int>::iterator I=S.end()-1 ; I >= S.begin() ; --I )
printf("%lf %lf\n",V[*I].x,V[*I].y);
}
int main ()
{
READ ();
SOLVE ();
OUT ();
return 0;
}