Pagini recente » Cod sursa (job #2063762) | Cod sursa (job #1938344) | Cod sursa (job #1150977) | Cod sursa (job #2447181) | Cod sursa (job #2288755)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
#define pp pair< double, double >
#define x first
#define y second
pp p[ 12005 ];
int st[ 12005 ], n, i, val;
double determinant( pp a, pp b, pp c )
{
double ans = a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - c.y * a.x - a.y * b.x;
return ans;
}
int main()
{
fin >> n;
for ( i = 1; i <= n; i++ )
{
fin>> p[ i ].x >> p[ i ].y;
}
sort( p + 1, p + n + 1 );
st[ ++st[ 0 ] ] = 1;
st[ ++st[ 0 ] ] = 2;
for ( i = 3; i <= n; i++ )
{
while ( st[ 0 ] >= 2 && determinant( p[ st[ st[ 0 ] - 1 ] ], p[ st[ st[ 0 ] ] ], p[ i ] ) > 0 )
{
st[ 0 ]--;
}
st[ ++st[ 0 ] ] = i;
}
for ( i = n - 1; i >= 1; i-- )
{
while ( determinant( p[ st[ st[ 0 ] - 1 ] ], p[ st[ st[ 0 ] ] ], p[ i ] ) > 0 )
{
st[ 0 ]--;
}
st[ ++st[ 0 ] ] = i;
}
st[ 0 ]--;
fout<< st[ 0 ] << '\n';
for ( i = st[ 0 ]; i >= 1; i-- )
{
fout<< fixed << setprecision ( 12 ) << p[ st[ i ] ].x << ' ' << p[ st[ i ] ].y << '\n';
}
return 0;
}