Pagini recente » Cod sursa (job #3193514) | Cod sursa (job #1093047) | Cod sursa (job #143250) | Cod sursa (job #2176875) | Cod sursa (job #1984466)
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <stack>
#include <iomanip>
#define ll long long
#define ld long double
#define pb push_back
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NLIM = 120000 + 10;
struct coordS
{
ld x, y;
};
int N;
coordS pont[NLIM];
ld dist2( coordS p1, coordS p2 )
{
return ( p2.x - p1.x ) * ( p2.x - p1.x ) + ( p2.y - p1.y ) * ( p2.y - p1.y );
}
int orient( coordS p1, coordS p2, coordS p3 )
{
ld val = ( p2.y - p1.y ) * ( p3.x - p2.x ) - ( p3.y - p2.y ) * ( p2.x - p1.x );
if( val < 0 )
return -1;// left
if( val > 0 )
return 1;// right
return 0;
}
int compar( const void* a, const void* b )
{
coordS p1 = *(coordS*)a;
coordS p2 = *(coordS*)b;
// -1 ha left
// 1 ha right
int ori = orient( pont[0], p1, p2 );
if( ori )
return ori;
// dist compar if collinear
if( dist2( pont[0], p1 ) > dist2( pont[0], p2 ) ) return 1;
if( dist2( pont[0], p1 ) < dist2( pont[0], p2 ) ) return -1;
return 0;
}
int main()
{
int st = 0;
fin >> N;
for( int i = 0; i < N; ++i )
{
fin >> pont[i].x;
fin >> pont[i].y;
if( pont[i].x < pont[st].x || ( pont[i].x == pont[st].x && pont[i].y < pont[st].y ) )
st = i;
}
coordS emp = pont[st];
pont[st] = pont[0];
pont[0] = emp;
qsort( pont + 1, N - 1, sizeof( coordS ), compar );
/*/
for( int i = 0; i < N; ++i )
{
cerr << i << ": " << pont[i].x << " " << pont[i].y << "\n";
}
//*/
stack< int > res;
res.push( 0 );
res.push( 1 );
//cout << orient()
for( int i = 2; i < N; ++i )
{
bool megy = 1;
while( megy )
{
megy = 0;
int i2 = res.top();
res.pop();
int i1 = res.top();
int ori = orient( pont[i1], pont[i2], pont[i] );
if( ori == -1 || ori == 0 )// left
res.push( i2 );
else if( ori == 1 )// right
megy = 1;
}
res.push( i );
}
fout << res.size() << "\n";
stack< int > resrev;
while( res.size() )
{
resrev.push( res.top() );
res.pop();
}
while( resrev.size() )
{
fout << fixed << setprecision( 6 ) << pont[resrev.top()].x << " " << pont[resrev.top()].y << "\n";
resrev.pop();
}
return 0;
}