Pagini recente » CLASAMENTUL!! | Istoria paginii runda/ems3/clasament | Autentificare | Profil ionutzm05 | Cod sursa (job #1058049)
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
#define P pair<double, double>
#define pb push_back
vector<P> queue,v;
P m;
long n, ind;
double x, y;
double dist ( P a, P b ) {
double x = b.first - a.first, y = b.second - a.first;
x *= x; y *= y;
return sqrt ( x + y );
}
double sin ( P source, P a ) {
if ( source.first == a.first )
return 1;
double sin = ( a.second - source.second ) / dist ( source, a );
return sin;
}
bool rightOfLine ( P a, P b, P c ) {
if ( a.first == b.first )
if ( b.second - a.second > 0 )
return c.first >= a.first;
else
return c.first < a.first;
if ( a.second == b.second )
if ( b.first - a.first > 0 )
return c.second <= a.second;
else
return c.second > a.second;
double p = ( a.second - b.second ) / ( a.first - b.first ), d = a.second - a.first * p;
double x = ( c.second - d ) / p;
if ( b.second - a.second > 0 ) {
if ( x < c.first )
return 1;
}
else if ( x > c.first )
return 1;
return 0;
}
bool comp ( P a, P b ) {
return sin ( m, a ) >= sin ( m, b );
}
int main()
{
freopen ( "infasuratoare.in", "rt", stdin );
freopen ( "infasuratoare.out", "wt", stdout );
scanf ( "%ld", &n );
scanf ( "%lf %lf", &m.first, &m.second );
for ( long i = 2; i <= n; i++ ) {
scanf ( "%lf %lf", &x, &y );
if ( x < m.first || ( x == m.first && y < m.second ) ) {
v.pb ( m );
m.first = x; m.second = y;
}
else
v.pb ( make_pair ( x, y ) );
}
sort ( v.begin ( ), v.end ( ), comp );
queue.pb ( m );queue.pb ( v[0] );ind = 1;
while ( ind < n - 1 ) {
while ( queue.size () > 1 && !rightOfLine ( queue[queue.size ( ) - 2], queue[queue.size ( ) - 1], v[ind] ) )
queue.pop_back ( );
queue.push_back ( v[ind] );
ind++;
}
printf ( "%ld\n", queue.size ( ) );
for ( long i = 0; i < queue.size ( ); i++ )
printf ( "%lf %lf\n", queue[i].first, queue[i].second );
return 0;
}